CF1553I Stairs

对于 $1$ 到 $n$ 的一个排列 $p$，我们定义阶梯数组 $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$，你的任务是计算有多少个排列的阶梯数组等于 $a$。由于答案可能很大，请输出对 $998\,244\,353$ 取模的结果。注意，这个数可能为零。

第一行输入一个整数 $n$（$1 \le n \le 10^5$），表示阶梯数组 $a$ 的长度。 第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。

输出一个整数，表示阶梯数组等于 $a$ 的排列个数，对 $998\,244\,353$ 取模。

由 ChatGPT 4.1 翻译