問題文

長さ N の数列 A=(A_1,A_2,\dots,A_N) が与えられます。この A に対して、i=1,2, \dots, N-1 の順に、以下の操作を行います。

• A_i と A_{i+1} を入れ替えるか、または何もしない。

操作後の数列として考えられるものの個数を 998244353 で割った余りを出力してください。

制約

• 入力は全て整数
• 1 \leq N \leq 10^6
• 1 \leq A_i \leq N

入力例 1

5
1 2 1 2 3

出力例 1

10

操作後の数列として考えられるのは以下の 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)

入力例 2

9
3 1 6 2 2 7 7 6 6

出力例 2

104