1346: #2273. 「JXOI2017」数列

Memory Limit:512 MB Time Limit:2.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

  • 1≤Ai≤ri1\leq A_i \leq r_i1Airi
  • 对于任意 3≤i≤n3 \leq i \leq n3in ,令 RRRA1A_1A1Ai−2A_{i-2}Ai2 中大于等于 Ai−1A_{i-1}Ai1 的最小值, LLLA1A_1A1Ai−2A_{i-2}Ai2 中小于等于 Ai−1A_{i-1}Ai1 的最大值。AiA_iAi 必须满足 L≤Ai≤RL \leq A_i \leq RLAiR。如果不存在大于等于 Ai−1A_{i-1}Ai1 的,那 么 R=+∞R = +\inftyR=+ ;如果不存在小于等于 Ai−1A_{i-1}Ai1 的,那么 L=

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

输入格式

第一行输入一个整数 nnn ,第二行输入 nnn 个整数 rir_iri

输出格式

输出一个整数表示方案数,答案可能很大,对 998244353998244353998244353 取模后输出。

样例

1.4 样例输入

3
2 2 2

1.5 样例输出

6

1.6 样例解释

满足条件的序列有 [1,1,1],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,2][1, 1, 1], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2, 2, 2][1,1,1],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,2]

数据范围与提示

测试点编号 nnn aia_iai
111 ≤7\leq 77 ≤7\leq 77
222
333 ≤50\leq 5050 ≤10\leq 1010
444
555 ≤16\leq 1616
666
777 ≤50\leq 5050
888
999 ≤150\leq 150150
101010