Description

Jiutiao Kelian (pinyin) has an integer sequence $r_i$ of length $n$. She now wants to construct an integer sequence $A$ of length $n$ that satisfies the following:

• $1 \le A_i \le r_i$.

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

Now she 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 \ne B_i$.

Input Format

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

Output Format

Output a single integer denoting the number of valid sequences. The answer can be large; output it modulo $998244353$.

3
2 2 2

6

Hint

For example, when $n = 3$ and $r_i = 2$ for all $i$, the valid sequences are $[1, 1, 1], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2, 2, 2]$.

Constraints:

Translated by ChatGPT 5