AT_arc230_c.Buildings

You are given an integer $N$ that is at least $2$, and $N-1$ integers $C_1,C_2,\dots ,C_{N-1}$.

There are $N$ buildings lined up on a number line. The $i$-th building stands at position $i$ and has height $H_i$. It is known that $(H_1,H_2,\dots ,H_N)$ is a permutation of $(1,2,\dots ,N)$, but the specific values of $H_1,H_2,\dots ,H_N$ are not known.

Find the number, modulo $998244353$, of possible sequences $(H_1,H_2,\dots, H_N)$ such that the following condition holds for all of $x=1,2,\dots, N-1$.

• The number of buildings visible from position $x+0.5$ is $C_x$. Here, the $i$-th building is visible if and only if there is no building with height greater than $H_i$ between position $x+0.5$ and position $i$.

给定一个不小于 $2$ 的整数 $N$，以及 $N-1$ 个整数 $C_1,C_2,\dots ,C_{N-1}$。

在一条数轴上并排矗立着 $N$ 栋建筑。第 $i$ 栋建筑位于位置 $i$，其高度为 $H_i$。已知 $(H_1,H_2,\dots ,H_N)$ 是 $(1,2,\dots ,N)$ 的一个排列，但 $H_1,H_2,\dots ,H_N$ 的具体取值未知。

求满足以下条件的序列 $(H_1,H_2,\dots, H_N)$ 的个数（对 $998244353$ 取模）：

• 对每个 $x = 1,2,\dots, N-1$，从位置 $x+0.5$ 处可见的建筑数量恰好为 $C_x$。
  其中，第 $i$ 栋建筑可见，当且仅当在位置 $x+0.5$ 与位置 $i$ 之间不存在高度严格大于 $H_i$ 的建筑。

The input is given from Standard Input in the following format:

$N$
$C_1$ $C_2$ $\dots$ $C_{N-1}$

输入从标准输入中按以下格式给出：

$N$
$C_1$ $C_2$ $\dots$ $C_{N-1}$

Output the answer.

输出答案。

Sample 1 Explanation:
For example, $(H_1,H_2,H_3,H_4)=(3,4,2,1)$ satisfies the condition. Indeed,

• For $x=1$, the buildings visible from position $x+0.5=1.5$ are the first and second buildings; there are $2=C_1$ such buildings.

• For $x=2$, the buildings visible from position $x+0.5=2.5$ are the second and third buildings; there are $2=C_2$ such buildings.

• For $x=3$, the buildings visible from position $x+0.5=3.5$ are the second, third, and fourth buildings; there are $3=C_3$ such buildings.

There are three sequences $(H_1,H_2,H_3,H_4)$ satisfying the condition, including this one.

Sample 2 Explanation:
There may be no sequence $(H_1,H_2,\dots, H_N)$ satisfying the condition.

Constraints

• $2\le N\le 2\times 10^5$
• $1\le C_x\le N$
• All input values are integers.

样例 1 解释：
例如，$(H_1,H_2,H_3,H_4)=(3,4,2,1)$ 满足条件。事实上，

• 当 $x=1$ 时，从位置 $x+0.5=1.5$ 处可见的建筑物为第一栋和第二栋；这样的建筑物共有 $2=C_1$ 栋。

• 当 $x=2$ 时，从位置 $x+0.5=2.5$ 处可见的建筑物为第二栋和第三栋；这样的建筑物共有 $2=C_2$ 栋。

• 当 $x=3$ 时，从位置 $x+0.5=3.5$ 处可见的建筑物为第二栋、第三栋和第四栋；这样的建筑物共有 $3=C_3$ 栋。

满足条件的序列 $(H_1,H_2,H_3,H_4)$ 共有三个，本例即为其中之一。

样例 2 解释：
可能不存在满足条件的序列 $(H_1,H_2,\dots, H_N)$。

约束条件

• $2\le N\le 2\times 10^5$
• $1\le C_x\le N$
• 所有输入值均为整数。