1346: #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​​ 。