Counting Permutations with Mex‐Interval Constraints

You are given a permutation \(p = [p_1, p_2, \dots, p_n]\) of \(\{0,1,\dots,n-1\}\). For each \(i\) with \(0 \le i \le n-1\) there is a positive integer constraint \(L_i\) meaning that there must exist at least one contiguous subarray (i.e. an interval \([l,r]\) with \(r-l+1 = L_i\)) whose \(\mathrm{mex}\) is exactly \(i\). Here, the \(\mathrm{mex}\) of a set of numbers is defined as the smallest nonnegative integer that does not appear in that set.

In other words, for every \(i\), there must exist an interval \([l,r]\) satisfying

[ {p_l, p_{l+1}, \dots, p_r} \supseteq {0,1,\dots,i-1} \quad\text{and}\quad i \notin {p_l, p_{l+1}, \dots, p_r}, ]

with \(r-l+1 = L_i\>.

It can be proved that if for every \(i \ge 1\) the constraint \(L_i\) satisfies

[ i \le L_i \le n-1, ]

then the only permutations that can possibly work are exactly those generated by starting with \(0\) and then inserting each subsequent number \(i\) (for \(1 \le i \le n-1\)) either at the beginning or at the end of the current sequence. (Such permutations are sometimes called extremal permutations.) There are \(2^{n-1}\) of them. Notice also that for each \(i \ge 1\) in any such permutation the numbers \(0, 1, \dots, i-1\) appear consecutively – so one may always take the contiguous block containing them (or a suitable extension of it) to achieve an interval of length at least \(i\) and at most \(n-1\) with \(\mathrm{mex}\, i\>.

The only subtle condition remains for \(i=0\). For \(\mathrm{mex}\,0\) one needs an interval that does not contain \(0\). In a permutation where \(0\) is at position \(pos\), one can take an interval entirely in the prefix (of length \(pos-1\)) or entirely in the suffix (of length \(n-pos\)). Hence, a necessary and sufficient condition for the \(0\)-constraint is that \(L_0\) does not exceed \(\max(pos-1, n-pos)\). In the extremal construction the position of \(0\) is determined by the number \(c\) of times a new element was inserted at the left: if there were \(c\) left insertions then \(0\) lands at position \(c+1\) and the maximum available interval length avoiding \(0\) is \(\max(c, n-c-1)\>.

Your task is to count the number of extremal permutations that satisfy all the \(n\) constraints. Since the answer can be very large, output it modulo \(998244353\).

Note: If for some \(i \ge 1\) the constraint does not satisfy \(i \le L_i \le n-1\), then no permutation can satisfy the conditions and the answer is 0.

inputFormat

The input begins with a single integer \(n\) \( (1 \le n)\). The next line contains \(n\) space‐separated positive integers \(L_0, L_1, \dots, L_{n-1}\). It is guaranteed that \(L_i\) is a positive integer.

outputFormat

Output a single integer: the number of valid permutations satisfying the given constraints, modulo \(998244353\).

sample

3
2 1 2

2