長さ $N$ の数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます。この数列 $A$ に対して、$i = 1, 2, \dots, N - 1$ の順に以下の操作を行います:
- $A_i$ と $A_{i+1}$ を入れ替えるか、何もしない。
これらの操作を行った後に得られる相異なる数列の個数を $998244353$ で割った余りを求めてください。
入力
入力は以下の形式で与えられます:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- 入力はすべて整数である。
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
出力
答えを $1$ 行で出力してください。
入出力例
入力例 1
5 1 2 1 2 3
出力例 1
10
入力例 2
9 3 1 6 2 2 7 7 6 6
出力例 2
104
注記
$1$ 番目の例では、操作を行った後に得られる可能性のある数列は $10$ 通りあります。それらの数列は以下の通りです:
- $(1, 2, 1, 2, 3)$,
- $(1, 2, 1, 3, 2)$,
- $(1, 2, 2, 1, 3)$,
- $(1, 2, 2, 3, 1)$,
- $(1, 1, 2, 2, 3)$,
- $(1, 1, 2, 3, 2)$,
- $(2, 1, 1, 2, 3)$,
- $(2, 1, 1, 3, 2)$,
- $(2, 1, 2, 1, 3)$,
- $(2, 1, 2, 3, 1)$.