問題文

Enjapma くんは、(1, 2, \ldots, N) の順列 P = (P_1, P_2, \ldots, P_N) を持っています。

Enjapma くんは、以下の操作をちょうど 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 点が与えられる。

入力例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