C - Monotonically Non-Decreasing Sequences

2 secs 1024 MB
kusirakusira's icon kusirakusira

配点 : 100点

問題文

NN 個の整数 A1,A2,...,ANA_1, A_2, ..., A_N があります。

(1,2,...,N)(1, 2, ..., N) の順列 P=(P1,P2,...,PN)P = (P_1, P_2, ..., P_N) であって次の条件を満たすものの個数を求めてください:

  • 1iN11 \leq i \leq N-1 なる任意の整数 ii について、次が成り立つ:
    • APiAPi+1\displaystyle \Large A_{P_i} \leq A_{P_{i + 1}}

ただし、答えは非常に大きくなる場合があるので、998244353998244353 で割ったあまりを出力してください。

制約

  • 1N3×1051 \leq N \leq 3 \times 10^5
  • 0Ai<230(1iN)0 \leq A_i < 2^{30} \scriptsize \; (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

入力は、以下の形式で標準入力から与えられる:

NN
A1A2ANA_1 \enspace A_2 \enspace \ldots \enspace A_N

出力

答えを求め、998244353998244353 で割ったあまりを標準出力へ出力せよ。


入出力例1

入力
3
3 1 5
出力
1

P=(2,1,3)P = (2, 1, 3) のみが条件を満たします。


入出力例2

入力
5
3 1 4 1 5
出力
2

P{(2,4,1,3,5),(4,2,1,3,5)}P \in \{\, (2, 4, 1, 3, 5), (4, 2, 1, 3, 5) \,\} のとき、またこのときに限り、条件が満たされます。


入出力例3

入力
9
1 4 1 4 2 1 3 5 6
出力
12 

提出


Go (1.21)