P10741 [SEERC 2020] Fence Job

题目描述

Fred 有一个长度为 $n$ 的排列 $h$，每次操作他可以选择一段区间 $[l,r]$，令 $h_i = \min_{j=l}^{r}h_j\ (i \in [l,r])$。

问进行若干次操作（可以为 $0$ 次）后不同的数组数量，对 $10^9 + 7$ 取模。

输入格式

第一行一个整数 $n\ (1 \leq n \leq 3000)$。

接下来一行 $n$ 个整数 $h_i\ (1 \leq h_i \leq n)$。

输出格式

输出操作后不同数组的数量模 $10^9+7$ 的值。

输入输出样例 #1

输入 #1

3
1 3 2

输出 #1

4

输入输出样例 #2

输入 #2

5
1 2 3 4 5

输出 #2

42

输入输出样例 #3

输入 #3

7
1 4 2 5 3 6 7

输出 #3

124