Kanan has an integer sequence $r_i$ of length $n$. She wants to construct an integer sequence $A$ of length $n$ that satisfies the following conditions:

• $1 \leq A_i \leq r_i$.
• For any $3 \leq i \leq n$, let $R$ be the minimum value among $A_1$ to $A_{i-2}$ that is greater than or equal to $A_{i-1}$, and let $L$ be the maximum value among $A_1$ to $A_{i-2}$ that is less than or equal to $A_{i-1}$. $A_i$ must satisfy $L \leq A_i \leq R$. If there is no value greater than or equal to $A_{i-1}$, then $R = +\infty$; if there is no value less than or equal to $A_{i-1}$, then $L = -\infty$.

Kanan wants to know how many different sequences satisfy these conditions. Two sequences $A$ and $B$ are different if and only if there exists at least one position $i$ such that $A_i \neq B_i$.

Input

The first line contains an integer $n$. The second line contains $n$ integers $r_i$.

Output

Output an integer representing the number of valid sequences. Since the answer may be very large, output it modulo $998244353$.

Examples

Input 1

3
2 2 2

Output 1

6

Note 1

The sequences satisfying the conditions are $[1, 1, 1], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2, 2, 2]$.

Subtasks

For all test cases, it is guaranteed that $n \geq 1$ and $r_i \geq 1$.