Non-equal Neighbours

题意翻译

给你一个正整数序列 $a_1,a_2,...a_n$，计算有多少个正整数序列 $b_1,b_2,...b_n$， 满足： 1. $1\le b_i \le a_i$，$i\in [1,n]$ 2. $b_i\neq b_{i+1}$，$i\in [1,n)$ 答案对 998244353 取模。

题目描述

You are given an array of $ n $ positive integers $ a_1, a_2, \ldots, a_n $ . Your task is to calculate the number of arrays of $ n $ positive integers $ b_1, b_2, \ldots, b_n $ such that: - $ 1 \le b_i \le a_i $ for every $ i $ ( $ 1 \le i \le n $ ), and - $ b_i \neq b_{i+1} $ for every $ i $ ( $ 1 \le i \le n - 1 $ ). The number of such arrays can be very large, so print it modulo $ 998\,244\,353 $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the array $ a $ . The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ).

输出格式

Print the answer modulo $ 998\,244\,353 $ in a single line.

输入输出样例

输入样例 #1

3
2 2 2

输出样例 #1

2

输入样例 #2

2
2 3

输出样例 #2

4

输入样例 #3

3
1 1 1

输出样例 #3

0

说明

In the first test case possible arrays are $ [1, 2, 1] $ and $ [2, 1, 2] $ . In the second test case possible arrays are $ [1, 2] $ , $ [1, 3] $ , $ [2, 1] $ and $ [2, 3] $ .