题目描述

長さ $N$ の整数列 $A_1,A_2,\ldots,A_N$ が与えられます。長さ $N$ の整数列 $X_1,X_2,\ldots,X_N$ であって、以下の条件をすべて満たすものはいくつあるか求め、$998244353$ で割った余りを出力してください。

• $1\ \leq\ X_i\ \leq\ A_i$
• $X_i\ \neq\ X_{i+1}\ (1\ \leq\ i\ \leq\ N-1)$

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

答えを出力せよ。

题目大意

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots ,a_n$，输出满足如下条件的序列 $x$ 的方案数：

1. $1\leq x_i\leq a_i$
2. $x_i\neq x_{i+1}(1\leq i\leq n-1)$

• $2\le n\le 5\times 10^5,1\le a_i\le 10^9$

3
2 3 2

6

10
158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202

524691026

提示

制約

• $2\ \leq\ N\ \leq\ 5\ \times\ 10^5$
• $1\ \leq\ A_i\ \leq\ 10^9$

Sample Explanation 1

条件をすべて満たす整数列は以下の $6$ 通りです。 - $1,2,1$ - $1,3,1$ - $1,3,2$ - $2,1,2$ - $2,3,1$ - $2,3,2$