Mex Permutations

Initially, there is an array $a$ of $n$ integers. It is known, that all its elements are in range $[0;n-1]$ and they are pairwise distinct. In other words, $a$ is a permutation.

Let's denote $mex(S)$ the minimal non-negative integer that does not belong to the set $S$. For example, $mex(\{1,2,3\})$ = $0$, $mex(\{0,1,3\})$ = $2$, $mex(\{0,1,2\})$ = $3$.

Array $F$ is being built in such a way, that $F_i$ = $mex(a_1,a_2,\dots ,a_{i-1},a_i)$. Let's denote $f(a)$ = $F$.

It is quite easy to build array $F$ by given array $a$, but unfortunately, array $a$ was lost. You wanted to restore it using array $F$, but there appeared to be too many possible arrays. You want to know how many arrays $a$ exists, such that $f(a)$ = $F$ modulo $998244353$.

Input

The first line of input contains one integer $n$ ($1\le n\le 10^6$) — length of the permutation.

The second line of input contains $n$ integers $F_i$ ($0\le F_i\le n+1$) — elements of array $F$.

Output

Print one integer — number of arrays $a$ that satisfy $f(a)$ = $F$ modulo $998244353$.

Examples

Scoring

1. ($3$ points): $F_i=n+1$;

2. ($3$ points): $F_i<F_{i+1}$ for all $i<n$;

3. ($5$ points): $n\le 3$;

4. ($16$ points): $n\le 7$;

5. ($18$ points): $n\le 18$;

6. ($27$ points): $n\le 1000$;

7. ($28$ points): no additional restrictions.