Semi-Permutations

問題文

蝉のセミくんは、以下の条件を満たす数列 $X$ を 準順列 と定義することにしました。

• ある $1$ 以上の整数 $K$ が存在して、数列 $(1,\ 2,\cdots ,K)$ から要素を１つだけ消去し、それを並び替えることによって $X$ を作ることができる。

なお、上記の定義から空の数列 $()$ も準順列であることに注意してください。

長さ $N$ の数列 $A$ が与えられるので、$A$ の連続とは限らない部分列であって、準順列であるようなものの個数を $998244353$ で割ったあまりを求めてください。

入力

制約

• $1\le N\le 10^5$
• $1\le A_i\le N+1$
• 入力は全て整数

出力

答えを $\bmod{998244353}$ で出力してください。

入力例１

3
3 1 4

出力例1

4

$()$、$(1)$、$(3,1)$、$(3,1,4)$ の４つが準順列になっています。
例えば、$(3,1)$ は $K=3$ とし、$(1,2,3)$ から $2$ を消去して並び替えることで得られます。

入力例2

4
3 4 3 5

出力例2

1

条件を満たす部分列は $()$ のみです。

入力例3

17
5 2 7 7 1 6 3 1 5 3 6 1 6 3 4 2 4

出力例3

2511