[JXOI2017] 数列
题目描述
九条可怜手上有一个长度为 $n$ 的整数数列 $r_i$,她现在想要构造一个长度为 $n$ 的,满足如下条件的整数数列 $A$ :
- $1 \le A_i \le r_i$
- 对于任意 $3 \le i \le n$ ,令 $R$ 为 $A_1$ 至 $A_{i-2}$ 中大于等于 $A_{i-1}$ 的最小值,$L$ 为 $A_1$ 至 $A_{i-2}$ 中小于等于 $A_{i-1}$ 的最大值。$A_i$ 必须满足 $L \le A_i \le R$ 。如果不存在大于等于 $A_{i-1}$ 的,那么 $R=+\infty$ ;如果不存在小于等于 $A_{i-1} $ 的,那么 $L = -\infty$ 。
现在可怜想要知道共有多少不同的数列满足这个条件。两个数列 $A$ 和 $B$ 是不同的当且仅当至少存在一个位置 $i$ 满足 $A_i \neq B_i$ 。
输入输出格式
输入格式
第一行输入一个整数 $n$ ,第二行输入 $n$ 个整数$ r_i$。
输出格式
输出一个整数表示方案数,答案可能很大,对 $998244353$ 取模后输出。
## 说明
满足条件的序列有 $[1, 1, 1], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2, 2, 2]$
输入输出样例
输入样例 #1
3
2 2 2
输出样例 #1
6
说明
| 测试点编号 | $n$ | $r_i$ |
| :----------: | :----------: | :----------: |
| $1,2$ | $n\le7$ | $r_i\le7$ |
| $3,4$ | $n\le50$ | $r_i\le10$ |
| $5,6$ | $n\le50$ | $r_i\le16$ |
| $7,8$ | $n\le50$ | $r_i\le50$ |
| $9,10$ | $n\le50$ | $r_i\le150$ |