※1209と1210は制約のみ違う同じ問題です。
問題
以下の条件を満たす数列$B_1,B_2,\dots,B_M$を増加数列と定義します。
- $1 \le M$
- $1 \le i < j \le M$を満たす任意の$(i, j)$について、$B_i < B_j$
例えば、{$1, 2, 3$}や{$2, 4, 6$}, {$1, 3, 9, 17$}は増加数列ですが、{$3, 2, 1$}や{$10, 2, 8$}は増加数列ではありません。
長さ$N$の順列$A_1, A_2, \dots, A_N$が与えられます。その中からいくつかの数字を取り出し、元の順番のまま並べた数列が増加数列になっているような取り出し方の個数を求め、$998244353$で割った余りを出力してください。
入力
$N$ $A_1, A_2, \dots, A_N$
出力
問題の答えを一行に出力してください。
制約
- $1 \le N \le 10^5$
- $1 \le A_i \le N$
- $i \neq j$ならば$A_i \neq A_j$
入出力例
入力例1
3 1 3 2
出力例1
5
{$1$}, {$3$}, {$2$}, {$1, 3$}, {$1, 2$}が該当します。
入力例2
5 1 4 3 2 5
出力例2
15
入力例3
8 8 2 1 5 7 3 6 4
出力例3
30