A14397. Stairs

For a permutation $p$ of numbers $1$ through $n$ , we define a stair array $a$ as follows: $a_i$ is length of the longest segment of permutation which contains position $i$ and is made of consecutive values in sorted order: $[x, x+1, \ldots, y-1, y]$ or $[y, y-1, \ldots, x+1, x]$ for some $x \leq y$ . For example, for permutation $p = [4, 1, 2, 3, 7, 6, 5]$ we have $a = [1, 3, 3, 3, 3, 3, 3]$ .

You are given the stair array $a$ . Your task is to calculate the number of permutations which have stair array equal to $a$ . Since the number can be big, compute it modulo $998\,244\,353$ . Note that this number can be equal to zero.

The first line of input contains integer $n$ ( $1 \le n \le 10^5$ ) — the length of a stair array $a$ .

The second line of input contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le n$ ).

Print the number of permutations which have stair array equal to $a$ . Since the number can be big, compute it modulo $998\,244\,353$ .