Stairs

给定一个长度为 $n$ 的排列 $p$。 令其中第 $i$ 个位置的权值为 $p$ 中最长的包含 $i$ 的连续自然数按顺序组成的区间的长度。例如，$p=[4,1,2,3,7,6,5]$ 中，第 $6$ 个位置的权值为 $[5,7]$ 的长度，第 $2$ 个位置的权值为 $[2,4]$ 的长度。 将这些权值依次拼在一起，就得到了 $p$ 的「阶梯序列」。 给定 $a$，你需要求出存在多少个 $p$，使得 $a$ 为 $p$ 的「阶梯序列」。答案对 $998244353$ 取模。

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 $ .

6
3 3 3 1 1 1

6

7
4 4 4 4 3 3 3

6

1
1

1

8
2 2 2 2 2 2 1 1

370

4
3 2 3 1

0