#P5320. [Jxoi2017]数列

    ID: 4333 传统题 2000ms 512MiB 尝试: 51 已通过: 26 难度: 8 上传者: 标签>难度分类提高+/省选-构造与建模逆向思考动态规划计数 DP状态维度消除前缀和优化 DP滚动数组CF2400递推

[Jxoi2017]数列

[JXOI2017] 数列

题目描述

九条可怜手上有一个长度为 nn 的整数数列 rir_i,她现在想要构造一个长度为 nn 的,满足如下条件的整数数列 AA :

  • 1≤Ai≤ri1 \le A_i \le r_i
  • 对于任意 3≤i≤n3 \le i \le n ,令 RR 为 A1A_1 至 Ai−2A_{i-2} 中大于等于 Ai−1A_{i-1} 的最小值,LL 为 A1A_1 至 Ai−2A_{i-2} 中小于等于 Ai−1A_{i-1} 的最大值。AiA_i 必须满足 L≤Ai≤RL \le A_i \le R 。如果不存在大于等于 Ai−1A_{i-1} 的,那么 R=+∞R=+\infty ;如果不存在小于等于 Ai−1A_{i-1} 的,那么 L=−∞L = -\infty 。

现在可怜想要知道共有多少不同的数列满足这个条件。两个数列 AA 和 BB 是不同的当且仅当至少存在一个位置 ii 满足 Ai≠BiA_i \neq B_i 。

输入格式

从标准输入读入。第一行一个整数 nn ,第二行输入 nn 个整数 rir_i。

输出格式

向标准输出写出一个整数,表示方案数,答案可能很大,对 998244353998244353 取模后输出。

样例 #1

样例输入 #1

3
2 2 2

样例输出 #1

6

提示

样例说明

满足条件的六个序列是 [1,1,1][1,1,1]、[1,2,1][1,2,1]、[1,2,2][1,2,2]、[2,1,1][2,1,1]、[2,1,2][2,1,2]、[2,2,2][2,2,2]。

数据范围

测试点编号 nn rir_i
1,21,2 n≤7n\le7 ri≤7r_i\le7
3,43,4 n≤50n\le50 ri≤10r_i\le10
5,65,6 ri≤16r_i\le16
7,87,8 ri≤50r_i\le50
9,109,10 ri≤150r_i\le150