← 返回题目列表

Codeforces · 1585/F

F. 不相等的邻居

中文机器翻译题面 查看原题

给定一个由 $$$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]$$$。