Problem Description

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.

Input Format

The first line contains a positive integer $N$.

The second line contains $N$ positive integers $a_i$.

Output Format

Output one integer representing the answer.

3
2 3 1

3

4
2 1 4 3

6

Hint

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