AT_arc171_b [ARC171B] Chmax

[problemUrl]: https://atcoder.jp/contests/arc171/tasks/arc171_b $ (1,\ 2,\ \dots,\ N) $ の順列 $ P\ =\ (P_1,\ P_2,\ \dots,\ P_N) $ に対して $ F(P) $ を次の手順によって定義します。 - 数列 $ B\ =\ (1,\ 2,\ \dots,\ N) $ がある。 $ B_i\ \lt\ P_{B_i} $ を満たす整数 $ i $ が存在する間、次の操作を行う。 - $ B_i\ \lt\ P_{B_i} $ を満たす整数 $ i $ のうち最小のものを $ j $ とおく。そして、$ B_j $ を $ P_{B_j} $ に置き換える。 操作を終了した時点での $ B $ を $ F(P) $ と定義する。(操作が有限回で終了することは証明できる。) 長さ $ N $ の数列 $ A\ =\ (A_1,\ A_2,\ \dots,\ A_N) $ が与えられます。 $ (1,2,\dots,N) $ の順列 $ P $ であって $ F(P)\ =\ A $ を満たすものは何個ありますか？答えを $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

$ F(P)\ =\ A $ を満たす順列 $ P $ の個数を $ 998244353 $ で割った余りを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ N $ - 入力される値は全て整数 ### Sample Explanation 1 例えば $ P\ =\ (2,\ 3,\ 1,\ 4) $ とする時、 $ F(P) $ は以下の手順で $ (3,\ 3,\ 3,\ 4) $ に決定します。 - はじめ、$ B\ =\ (1,\ 2,\ 3,\ 4) $ である。 - $ B_i\ \lt\ P_{B_i} $ を満たす整数 $ i $ のうち最小のものは $ 1 $ である。$ B_1 $ を $ P_{B_1}\ =\ 2 $ に置き換えて、$ B\ =\ (2,\ 2,\ 3,\ 4) $ となる。 - $ B_i\ \lt\ P_{B_i} $ を満たす整数 $ i $ のうち最小のものは $ 1 $ である。$ B_1 $ を $ P_{B_1}\ =\ 3 $ に置き換えて、$ B\ =\ (3,\ 2,\ 3,\ 4) $ となる。 - $ B_i\ \lt\ P_{B_i} $ を満たす整数 $ i $ のうち最小のものは $ 2 $ である。$ B_2 $ を $ P_{B_2}\ =\ 3 $ に置き換えて、$ B\ =\ (3,\ 3,\ 3,\ 4) $ となる。 - $ B_i\ \lt\ P_{B_i} $ を満たす $ i $ は存在しないので、操作を終了する。この時点での $ B\ =\ (3,\ 3,\ 3,\ 4) $ を $ F(P) $ として定義する。 $ F(P)\ =\ A $ を満たす順列 $ P $ は $ (2,\ 3,\ 1,\ 4) $ の $ 1 $ 通りのみです。