对于数字 $$$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