分数: 800 点
问题陈述
给你一系列 N 正整数: A=(A_1,A_2,\dots,A_N).
有多少个整数序列 B 由之间的整数组成 1 和 N (含)满足以下所有条件?打印计数模数 998244353.
- 对于每个整数 i 这样 1 \le i \le N,正好有 A_i 出现 i in B.
- 对于每个整数 i 这样 1 \le i \le |B|-1,它认为 |B_i - B_{i+1}|=1.
约束
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 2 \times 10^5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
3 2 3 1
示例输出 1
6
B 可以是以下六个序列。
- (1,2,1,2,3,2)
- (1,2,3,2,1,2)
- (2,1,2,1,2,3)
- (2,1,2,3,2,1)
- (2,3,2,1,2,1)
- (3,2,1,2,1,2)
因此,答案是 6.
示例输入 2
1 200000
示例输出 2
0
可能没有满足条件的序列。
示例输入 3
6 12100 31602 41387 41498 31863 12250
示例输出 3
750337372