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

对于数字 $1$ 到 $n$ 的一个排列 $p$，我们定义其阶梯数组（stair array）$a$ 如下：$a_i$ 表示包含位置 $i$ 的最长连续段的长度，该连续段在排列中占据连续的位置，且其中的数值构成一个严格递增或严格递减的连续整数区间：即形如 $[x, x+1, \ldots, y-1, y]$ 或 $[y, y-1, \ldots, x+1, x]$（其中 $x \leq y$）。例如，对排列 $p = [4, 1, 2, 3, 7, 6, 5]$，其对应的阶梯数组为 $a = [1, 3, 3, 3, 3, 3, 3]$。

现给定阶梯数组 $a$，你的任务是计算有多少个长度为 $n$ 的排列 $p$ 满足其阶梯数组恰好等于 $a$。由于结果可能很大，请将答案对 $998\,244\,353$ 取模输出。注意，该数目可能为零。

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

输入的第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 表示楼梯数组 $a$ 的长度。

输入的第二行包含 $n$ 个整数 $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$.

输出满足楼梯数组等于 $a$ 的排列数量。由于该数值可能很大，请对 $998\,244\,353$ 取模。