P10741 [SEERC 2020] Fence Job

Fred has a permutation $h$ of length $n$. In each operation, he can choose an interval $[l,r]$ and set $h_i = \min_{j=l}^{r} h_j\ (i \in [l,r])$. After performing several operations (possibly $0$ operations), find the number of distinct arrays that can be obtained, modulo $10^9 + 7$.

The first line contains an integer $n\ (1 \leq n \leq 3000)$. The next line contains $n$ integers $h_i\ (1 \leq h_i \leq n)$.

Output the number of distinct arrays after the operations modulo $10^9 + 7$.

Translated by ChatGPT 5