P4063 [JXOI2017] Sequence

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$.

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

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

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: | Test point ID | $n$ | $r_i$ | | :----------: | :----------: | :----------: | | $1, 2$ | $n \le 7$ | $r_i \le 7$ | | $3, 4$ | $n \le 50$ | $r_i \le 10$ | | $5, 6$ | $n \le 50$ | $r_i \le 16$ | | $7, 8$ | $n \le 50$ | $r_i \le 50$ | | $9, 10$ | $n \le 50$ | $r_i \le 150$ | Translated by ChatGPT 5