問題文
Enjapma君是(1, 2, \ldots, N) 的排列 给出了 P = (P_1, P_2, \ldots, P_N) 。 来自
Enjapma-kun 执行以下操作。只是 执行 1 回。 满足
- 整数 k (\geq 0) 和 还给出了1 \leq l_1 \lt r_1 \lt l_2 \lt r_2 \lt \cdots \lt l_k \lt r_k \leq N 的整数序列 选择 (l_1, r_1, l_2, r_2, \ldots , l_k, r_k) 后,每个 按升序对 i (1 \leq i \leq k) ,P_{l_i}, P_{l_{i}+1}, \ldots, P_{r_i} 进行排序。
操作后 输出 P 的可能排列数为998244353 除的余数。 用
制約
- 所有输入均为整数。
- 1 \leq N \leq 2\times 10^5
- 1 \leq P_i \leq N
- P_1, P_2, \ldots, P_N 都是不同的。
部分点
- 1 \leq N \leq 3000 的数据集 给出 50 点。 如果您正确回答了所有满足
入力
输入按以下格式给出。
N P_1 P_2 \ldots P_N
出力
答案 请打印除以 1 行输出。
入力例1
4 3 2 4 1
出力例1
6
- k = 0 以P = (3, 2, 4, 1) 。
- k = 1 ,(l_1, r_1) = (1, 2) ,P = (2, 3, 4, 1) 。
- k = 1 ,(l_1, r_1) = (1, 4) ,P = (1, 2, 3, 4) 。
- k = 1 ,(l_1, r_1) = (2, 4) ,P = (3, 1, 2, 4) 。
- k = 1 ,(l_1, r_1) = (3, 4) ,P = (3, 2, 1, 4) 。
- k = 2 ,(l_1, r_1,l_2, r_2) = (1, 2, 3, 4) ,P = (2, 3, 1, 4) 。
还有其他的操作方法,但是上面的 6 将导致其中一条街道的重复。
入力例2
12 4 1 9 5 3 8 7 10 6 2 12 11
出力例2
300