题目描述

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

输出格式

请输出答案。

样例 1

输入

3
2 3 2

输出

6

样例 2

输入

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$

样例解释 1

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

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

由 ChatGPT 4.1 翻译