#P8815. [2023联测]还是序列
[2023联测]还是序列
还是序列
题目描述
你有一个长度为 的序列 ,现在你需要将这个序列划分成若干段。你需要保证,对于每一段,都有 $\mathit{m i n} ( S_{i} ) \leq\vert S \vert\leq\mathit{m a x} ( S_{i} )$。其中 是这一段 的最小值, 是这一段 的最大值, 是这一段的长度。
你需要求出所有的划分方案数,由于答案很大,你需要对 取模。
输入格式
一行一个正整数,表示序列 的长度。
接下来一行 个正整数,表示序列 。
输出格式
输出一行一个数 , 代表所有的划分方案数对 取模的结果。
样例输入1
7
1 6 2 3 4 3 4
样例输出1
6
样例2
见附加文件。
数据范围与提示
10%的数据满足 ;30%满足 。
另外10%满足 ;另外10%的 在 中随机取值;另外10%的 只有两种不同值;另外10%满足 ;另外10%满足 。
全部数据满足 ,序列元素为正整数。无需额外的元素数值上界:任意大于 的元素都可等价替换为 ,因为每一段的长度至多为 。