题目描述

给长度为 $N$ 和 $N-1$ 的正整数序列 $A$ 和 $B$，你可以进行以下操作任意次。

• 选择整数 $i$ 和 $j$($1\le i<j\le N$)，将 $A_i,A_j,B_i,B_{i+1}...B_{j-1}$ 减一。需要保证操作后不会出现负数。

令 $m$ 为可以执行的操作的次数的最大值，求出 $m$ 次操作后有多少种本质不同的序列 $A$（对 998244353 取模）。

• $1\le n\le 2\times 10^5$
• $1\le A_i\le 10^9$
• $1\le B_i\le 10^9$

样例 1

输入

3
1 2 2
1 2

输出

3

样例 2

输入

4
1 1 1 1
2 2 2

输出

1

样例 3

输入

4
2 2 3 4
3 1 4

输出

3