← 返回题目列表

Codeforces · 1553/I

I. 楼梯

中文机器翻译题面 查看原题

对于数字 $$$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$$$ 为模进行计算。

示例

输入 #1

6
3 3 3 1 1 1

输出 #1

6

输入 #2

7
4 4 4 4 3 3 3

输出 #2

6

输入 #3

1
1

输出 #3

1

输入#4

8
2 2 2 2 2 2 1 1

输出#4

370

输入 #5

4
3 2 3 1

输出 #5

0