시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 39 | 27 | 22 | 70.968% |
Fred the Farmer wants to redesign the fence of his house. Fred’s fence is composed of $n$ vertical wooden planks of various heights. The $i$-th plank’s height is $h_i$ ($1 \le h_i \le n$). Initially, all heights are distinct.
In order to redesign the fence, Fred will choose some contiguous segment $[l\dots r]$ of planks and “level” them, by cutting them in order to make all heights equal to the minimum height on that segment. More specifically, the new heights of the segment become $h'_i = \min{\{h_l, h_{l+1}, \dots, h_r\}}$ for all $l \le i \le r$.
How many different designs can Fred obtain by applying this procedure several (possibly $0$) times? Since the answer may be huge, you are required to output it modulo $10^9 + 7$.
Two designs $A$ and $B$ are different if there is some plank that has a different height in $A$ than in $B$.
The first line of the input contains $n$ ($1 \le n \le 3\,000$), the number of planks of Fred’s fence.
The second line contains $n$ distinct integers $h_i$ ($1 \le h_i \le n$, $1 \le i \le n$), the heights of each of the planks.
Output a single integer, the number of different possible fence designs that can be obtained, modulo $10^9 + 7$.
3 1 3 2
4
5 1 2 3 4 5
42
7 1 4 2 5 3 6 7
124