[JXOI2017] 数列
题目描述
九条可怜手上有一个长度为 n 的整数数列 ri,她现在想要构造一个长度为 n 的,满足如下条件的整数数列 A :
- 1≤Ai≤ri
- 对于任意 3≤i≤n ,令 R 为 A1 至 Ai−2 中大于等于 Ai−1 的最小值,L 为 A1 至 Ai−2 中小于等于 Ai−1 的最大值。Ai 必须满足 L≤Ai≤R 。如果不存在大于等于 Ai−1 的,那么 R=+∞ ;如果不存在小于等于 Ai−1 的,那么 L=−∞ 。
现在可怜想要知道共有多少不同的数列满足这个条件。两个数列 A 和 B 是不同的当且仅当至少存在一个位置 i 满足 Ai=Bi 。
输入格式
从标准输入读入。第一行一个整数 n ,第二行输入 n 个整数 ri。
输出格式
向标准输出写出一个整数,表示方案数,答案可能很大,对 998244353 取模后输出。
样例 #1
样例输入 #1
3
2 2 2
样例输出 #1
6
提示
样例说明
满足条件的六个序列是 [1,1,1]、[1,2,1]、[1,2,2]、[2,1,1]、[2,1,2]、[2,2,2]。
数据范围
| 测试点编号 |
n |
ri |
| 1,2 |
n≤7 |
ri≤7 |
| 3,4 |
n≤50 |
ri≤10 |
| 5,6 |
ri≤16 |
| 7,8 |
ri≤50 |
| 9,10 |
ri≤150 |