#P8815. [2023联测]还是序列

    ID: 8909 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>动态规划数据结构树状数组贪心CF2600分治ST表模拟

[2023联测]还是序列

还是序列

题目描述

你有一个长度为nn 的序列 {ai}\{a_i\},现在你需要将这个序列划分成若干段。你需要保证,对于每一段SS,都有 $\mathit{m i n} ( S_{i} ) \leq\vert S \vert\leq\mathit{m a x} ( S_{i} )$。其中min(Si)m i n ( S_{i} ) 是这一段aia_{i} 的最小值,max(Si)m a x ( S_{i} ) 是这一段aia_{i} 的最大值,∣S∣| S | 是这一段的长度。

你需要求出所有的划分方案数,由于答案很大,你需要对 109+710^{9}+7 取模。

输入格式

一行一个正整数nn,表示序列 {ai}\{a_i\} 的长度。

接下来一行nn 个正整数,表示序列 {ai}\{a_i\}。

输出格式

输出一行一个数 , 代表所有的划分方案数对 109+710^{9}+7 取模的结果。

样例输入1

7
1 6 2 3 4 3 4

样例输出1

6

样例2

见附加文件。

数据范围与提示

10%的数据满足 n≤20n\le20;30%满足 n≤1000n\le1000。

另外10%满足 n≤105,ai≤500n\le10^5,a_i\le500;另外10%的 aia_i 在 [1,n][1,n] 中随机取值;另外10%的 aia_i 只有两种不同值;另外10%满足 a2i=na_{2i}=n;另外10%满足 n≤105n\le10^5。

全部数据满足 1≤n≤5×1051\le n\le5\times10^5,序列元素为正整数。无需额外的元素数值上界:任意大于 nn 的元素都可等价替换为 n+1n+1,因为每一段的长度至多为 nn。