P7972 [KSN2021] Self Permutation

Given a permutation $a_i$ of length $N$, you may perform the following operation any number of times: - Choose two adjacent numbers and delete the larger one of them. Ask for the number of different sequences that can be obtained in the end. Output the answer modulo $10^9+7$. Note that if all numbers between two numbers are deleted, then they will become adjacent.

The first line contains a positive integer $N$. The second line contains $N$ positive integers $a_i$.

Output one integer representing the answer.

**Sample Explanation** For the first sample, the following are all possible sequences that can be obtained: - $[2,3,1]$ - $[\bold2,\bold3,1]\to[2,1]$ - $[\bold2,\bold3,1]→[\bold2,\bold1]→[1]$ For the second sample, the following are all possible sequences that can be obtained: - $[2,1,4,3]$ - $[\bold2,\bold1, 4, 3]\to[1, 4, 3]$ - $[\bold2,\bold1, 4, 3]\to[1,\bold4,\bold3]\to[1, 3]$ - $[\bold2,\bold1, 4, 3]\to[1,\bold4,\bold3]\to[\bold1,\bold3]\to[1]$ - $[2, 1,\bold4,\bold3]\to[2, 1, 3]$ - $[2, 1,\bold4,\bold3]\to[2,\bold1,\bold3]\to[2, 1]$ **Constraints** **This problem uses bundled testdata.** - Subtask 1 (8 points): There is only one test case, with $N=6$, $A=[2,5,1,3,4,6]$. - Subtask 2 (20 points): $N\leq 200$. - Subtask 3 (13 points): $N\leq 2000$, $A_i=i$. - Subtask 4 (9 points): $A_i=i$. - Subtask 5 (23 points): $N\leq 2000$. - Subtask 6 (27 points): No special restrictions. For all testdata, $N\leq 3\times 10^5$, and it is guaranteed that the input $a_i$ forms a permutation. Translated by ChatGPT 5