/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1800 点
問題文
長さ N の正整数列 A 及び長さ N-1 の正整数列 B が与えられます． あなたは，次の操作を好きな回数行うことができます．
- 整数 i,j (1 \leq i < j \leq N) を選び，A_i,A_j,B_i,B_{i+1},\cdots,B_{j-1} の値をそれぞれ 1 減らす． ただし，操作後に負になる値が存在してはならない．
ここで，操作を行える回数の最大値を m とおきます． m 回の操作後の A としてありえる数列が何通りあるかを 998244353 で割った余りを求めてください．
制約
- 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 としては以下の 3 通りが考えられます．
- 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
Score : 1800 points
Problem Statement
Given is a sequence A of N positive integers and a sequence B of N-1 positive integers. You can do the following operation any number of times.
- Choose integers i and j (1 \leq i < j \leq N) and decrease each of the following values by 1: A_i,A_j,B_i,B_{i+1},\cdots,B_{j-1}. Here, there should not be any negative value after this operation.
Let m be the maximum number of operations that can be done. Find the number, modulo 998244353, of sequences that A can be after m operations.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_{N-1}
Output
Print the answer.
Sample Input 1
3 1 2 2 1 2
Sample Output 1
3
We have m=2. After two operations, A will be one of the following three sequences.
- A=(1,0,0): we end up with this after operations with (i,j)=(2,3) and (i,j)=(2,3).
- A=(0,1,0): we end up with this after operations with (i,j)=(1,3) and (i,j)=(2,3).
- A=(0,0,1): we end up with this after operations with (i,j)=(1,2) and (i,j)=(2,3).
Sample Input 2
4 1 1 1 1 2 2 2
Sample Output 2
1
Note that we do not distinguish two scenarios with different contents of B if the contents of A are the same.
Sample Input 3
4 2 2 3 4 3 1 4
Sample Output 3
3