AT_utpc2020_e Sort Segments

[problemUrl]: https://atcoder.jp/contests/utpc2020/tasks/utpc2020_e 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 $ で割った余りを求めてください。

入力は以下の形式で与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

答えを $ 1 $ 行に出力せよ。

### 制約 - 入力は全て整数である。 - $ 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 $ 点が与えられる。 ### Sample Explanation 1 \- $ 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 $ 通りのいずれかと重複する結果になります。