2491: #2273. 「JXOI2017」数列

九条可怜手上有一个长度为 $n$ 的整数数列 rir_ir​i​​ ，她现在想要构造一个长度为 $n$ 的，满足如下条件的整数数列 $A$ :

• 1≤Ai≤ri1\leq A_i \leq r_i1≤A​i​​≤r​i​​ 。
• 对于任意 $3\le i\le n$ ，令 $R$ 为 A1A_1A​1​​ 至 Ai−2A_{i-2}A​i−2​​ 中大于等于 Ai−1A_{i-1}A​i−1​​ 的最小值， $L$ 为 A1A_1A​1​​ 至 Ai−2A_{i-2}A​i−2​​ 中小于等于 Ai−1A_{i-1}A​i−1​​ 的最大值。AiA_iA​i​​ 必须满足 L≤Ai≤RL \leq A_i \leq RL≤A​i​​≤R。如果不存在大于等于 Ai−1A_{i-1}A​i−1​​ 的，那 么 $R=+\infty$ ;如果不存在小于等于 Ai−1A_{i-1}A​i−1​​ 的，那么 $L=-\infty$ 。

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

输入格式

第一行输入一个整数 $n$ ，第二行输入 $n$ 个整数 rir_ir​i​​ 。

输出格式

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

样例

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]$ 。

数据范围与提示

测试点编号	$n$	aia_ia​i​​
$1$	$\le 7$	$\le 7$
$2$
$3$	$\le 50$	$\le 10$
$4$
$5$		$\le 16$
$6$
$7$		$\le 50$
$8$
$9$		$\le 150$
$10$