Problem Statement
Given is a sequence of N integers A1,A2,ldots,AN. Print the number, modulo 998244353, of sequences of N integers X1,X2,ldots,XN satisfying all of the following conditions:
- 1leqXileqAi
- XineqXi+1(1leqileqN−1)
Constraints
- 2leqNleq5times105
- 1leqAileq109
Input is given from Standard Input in the following format:
N
A1 A2 ldots AN
Output
Print the answer.
Sample Output 1
The following six sequences satisfy all of the conditions.
- 1,2,1
- 1,3,1
- 1,3,2
- 2,1,2
- 2,3,1
- 2,3,2
Sample Output 2