408342: GYM103102 F Fence Job

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 \leq h_i \leq n$$$). Initially, all heights are distinct.

In order to redesign the fence, Fred will choose some contiguous segment $$$[l...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}, ..., h_r \}$$$ for all $$$l \leq i \leq 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 \leq n \leq 3\,000$$$), the number of planks of Fred's fence.

The second line contains $$$n$$$ distinct integers $$$h_i$$$ ($$$1 \leq h_i \leq n, 1 \leq i \leq 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