AT_arc115_e.[ARC115E] LEQ and NEQ

给定一个长度为 $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$

请输出答案。

限制条件

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

样例解释 1

满足所有条件的整数序列共有以下 $6$ 种：

• $1,2,1$
• $1,3,1$
• $1,3,2$
• $2,1,2$
• $2,3,1$
• $2,3,2$

由 ChatGPT 4.1 翻译