分数: 700 点
问题陈述
给定的是一系列 N 整数 A_1,A_2,\ldots,A_N。打印数字,模数 998244353,序列 N 整数 X_1,X_2,\ldots,X_N 满足以下所有条件:
- 1 \leq X_i \leq A_i
- X_i \neq X_{i+1} (1 \leq i \leq N-1)
约束
- 2 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印答案。
示例输入 1
3 2 3 2
示例输出 1
6
以下六个序列满足所有条件。
- 1,2,1
- 1,3,1
- 1,3,2
- 2,1,2
- 2,3,1
- 2,3,2
示例输入 2
10 158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202
示例输出 2
524691026