不等数列

题目描述

小 Z 有一个长度为 $n$ 的序列 $A = (a_1, a_2, \dots, a_n)$。

小 Z 想知道：有多少个长度为 $n$ 的「好的」正整数序列 $B = (b_1, b_2, \dots, b_n)$，同时满足以下两个条件：

1. 对于任意 $i = 1, 2, \dots, n$，都有 $1 \le b_i \le a_i$；
2. 对于任意相邻的两个位置，都有 $b_i \neq b_{i+1}$（即相邻两项不能相等）。

由于满足条件的序列数量可能非常多，请输出答案对 $998244353$ 取模之后的结果。

输入格式

第一行包含一个整数 $n$，表示序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列 $A$ 的每个元素。

输出格式

输出一行，包含一个整数，表示满足条件的序列数量对 $998244353$ 取模的结果。

样例输入 #1

3
2 2 2

样例输出 #1

2

样例输入 #2

10
2 3 4 5 9 8 7 1 2 3

样例输出 #2

28722

样例输入 #3

50
98 123 123 42 55 67 82 10 23 20 98 123 123 42 55 67 81 10 23 20 98 123 123 42 55 67 89 10 23 20 98 123 124 42 55 67 89 10 23 20 98 123 123 42 55 67 89 10 23 20

样例输出 #3

149787148

数据范围

• 对于 $100\%$ 的数据：$1 \le n \le 10^6$，$1 \le a_i \le 10^9$。
• 答案对 $998244353$ 取模。

知识点与难度

本题涉及的知识点从属于 GESP 六级，难度等级：⭐⭐⭐。

测试点分布