Little K 拥有一个 $1 \sim n$ 的随机排列 $p_1, p_2, \dots, p_n$。他打算给他的朋友 Little Cyan Fish 出一道题。

Little K 可以选择该排列的一组子段，并将每个子段的最大值提供给 Little Cyan Fish。形式化地，他可以选择一个集合 $\{(l_1, r_1), (l_2, r_2), \dots, (l_k, r_k)\}$，其中对于每个 $1 \le i \le k$ 都有 $1 \le l_i \le r_i \le n$。Little Cyan Fish 将收到 $k$ 个元组 $(l_1, r_1, m_1), (l_2, r_2, m_2), \dots, (l_k, r_k, m_k)$，其中 $m_i = \max_{j=l_i}^{r_i} p_j$，表示 Little K 所选的每个子段的最大值。

Little Cyan Fish 必须猜出 Little K 的排列是什么。由于 Little K 是 Little Cyan Fish 最好的朋友，他需要确保根据所提供的信息能够唯一地猜出该排列。因此，满足 Little K 所提供信息的排列应当只有一个。

Little K 对能够提供给 Little Cyan Fish 并使其能唯一确定排列的子段集合的数量感到好奇。不幸的是，Little K 自己无法解决这个问题，所以他向你寻求帮助。由于答案可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^5$)。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$，$p_1, p_2, \dots, p_n$ 是 $1 \sim n$ 的一个排列)。保证该排列是从所有长度为 $n$ 的排列中均匀随机选择的。

输出格式

输出一行，包含一个整数，表示答案对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

2
1 2

样例输出 1

6

样例输入 2

4
1 4 2 3

样例输出 2

532