分数: 900 点
问题陈述
是否为非空非负整数序列 (V_1, V_2, \dots, V_M) is 波兰语 或 not 递归定义如下:
- 我们说 (V_1, V_2, \dots, V_M) 是波兰语(如果存在) V_1 波兰序列 W_1, W_2, \dots, W_{V_1} 这样序列的串联 (V_1), W_1, W_2, \dots, W_{V_1} 按此顺序等于 (V_1, V_2, \dots, V_M).
特别是,序列 (0) 是波兰语。
给定一个非负整数序列 (A_1, A_2, \dots, A_N) 长度 N,求长度为波兰序列的数量 N 按字典顺序不大于 (A_1, A_2, \dots, A_N),模数 998244353.
序列的字典顺序是什么?
我们说这个序列 S = (S_1,S_2,\ldots,S_{|S|}) is 按字典顺序排列较少 比序列 T = (T_1,T_2,\ldots,T_{|T|}) 如果下面的条件 1. 或 2. 成立。 在这里, |S|, |T| 代表的长度 分别为 S, T 。
- |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- 存在一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 使得以下两者成立:
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i (数字上)小于 T_i.
约束
- 1\leq N \leq 3\times 10^5
- 0\leq A_i \lt N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
打印满足条件的序列数,模数 998244353.
示例输入 1
6 1 1 1 2 0 0
示例输出 1
2
(1, 1, 1, 1, 1, 0) 和 (1, 1, 1, 2, 0, 0) 满足条件。
我们可以验证 (1, 1, 1, 2, 0, 0) 的波兰语如下。
- 如问题陈述中所述, (0) 是波兰语。
- (2, 0, 0) 是波兰语,因为它等于串联 (2) 和两个波兰序列 (0) 和 (0) 按此顺序。
- (1, 2, 0, 0) 是波兰语,因为它等于串联 (1) 和一个波兰序列 (2, 0, 0) 按此顺序。
- (1, 1, 2, 0, 0) 是波兰语,因为它等于串联 (1) 和一个波兰序列 (1, 2, 0, 0) 按此顺序。
- (1, 1, 1, 2, 0, 0) 是波兰语,因为它等于串联 (1) 和一个波兰序列 (1, 1, 2, 0, 0) 按此顺序。
示例输入 2
11 3 3 4 4 5 5 6 6 7 7 8
示例输出 2
13002
示例输入 3
19 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18
示例输出 3
477638700
示例输入 4
4 1 1 0 0
示例输出 4
0