分数: 1800 点
问题陈述
给定的是一个序列 A of N 正整数和序列 B of N-1 正整数。 您可以多次执行以下操作。
- 选择整数 i 和 j (1 \leq i < j \leq N)并将以下每个值减少 1: A_i,A_j,B_i,B_{i+1},\cdots,B_{j-1}。这里,此操作后不应有任何负值。
让 m 是可以完成的最大操作数。 求模数 998244353,序列 A 可以在之后 m 操作。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_{N-1}
输出
打印答案。
示例输入 1
3 1 2 2 1 2
示例输出 1
3
我们有 m=2。经过两次手术后, A 将是以下三个序列之一。
- A=(1,0,0):我们在操作后得到这个 (i,j)=(2,3) 和 (i,j)=(2,3).
- A=(0,1,0):我们在操作后得到这个 (i,j)=(1,3) 和 (i,j)=(2,3).
- A=(0,0,1):我们在操作后得到这个 (i,j)=(1,2) 和 (i,j)=(2,3).
示例输入 2
4 1 1 1 1 2 2 2
示例输出 2
1
请注意,我们不区分具有不同内容的两个场景 B 如果内容 A 是相同的。
示例输入 3
4 2 2 3 4 3 1 4
示例输出 3
3