给定一个由 $$$n$$$ 正整数 $$$a_1, a_2, \ldots, a_n$$$ 组成的数组。您的任务是计算 $$$n$$$ 正整数 $$$b_1, b_2, \ldots, b_n$$$ 的数组数量,使得:
- $$$1 \le b_i \le a_i$$$ 对于每个 $$$i$$$ ($$$1 \le i \le n$$$),并且
- $$$b_i \neq b_{i+1}$$$ 对于每个 $$$i$$$ ($$$1 \le i \le n - 1$$$)。
此类数组的数量可能非常大,因此将其打印为 $$$998\,244\,353$$$ 模。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
输出
在一行中打印对 $$$998\,244\,353$$$ 取模的答案。
示例
输入 #1
3 2 2 2
输出 #1
2
输入 #2
2 2 3
输出 #2
4
输入 #3
3 1 1 1
输出 #3
0
注意
在第一个测试用例中,可能的数组是 $$$[1, 2, 1]$$$ 和 $$$[2, 1, 2]$$$。
在第二个测试用例中,可能的数组是 $$$[1, 2]$$$、$$$[1, 3]$$$、$$$[2, 1]$$$ 和 $$$[2, 3]$$$。