← 返回题目列表

AtCoder · utpc2020_e

E. 对段进行排序

中文机器翻译题面 查看原题

問題文

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