Description

To achieve a better performance at the upcoming gala, Xiao A, the leader of the AAA choir, needs to arrange the choir members into a lineup based on their heights. Suppose there are $n$ people in total, the $i$-th person’s height is $h_i$ meters ($1000 \le h_i \le 2000$), and any two people have different heights. Suppose the final lineup consists of $n$ people standing in one row. To simplify the process, Xiao A came up with the following method: he first lets everyone stand in an initial lineup in an arbitrary order, and then, from left to right, inserts each person into the final lineup according to these rules:

• The first person is directly inserted into the empty current lineup.

• For each person starting from the second, if he is taller than the person immediately before him in the initial lineup ($h$ is larger), insert him at the right end of the current lineup. If he is shorter ($h$ is smaller), insert him at the left end.

After all $n$ people have been inserted into the current lineup, the final lineup is obtained.

For example, there are $6$ people in the initial lineup, with heights $1850, 1900, 1700, 1650, 1800, 1750$.
Then Xiao A will obtain the final lineup step by step as follows:

• 1850, 1900, because $1900 > 1850$.

• 1700, 1850, 1900, because $1700 < 1900$.

• 1650, 1700, 1850, 1900, because $1650 < 1700$.

• 1650, 1700, 1850, 1900, 1800, because $1800 > 1650$.

• 1750, 1650, 1700, 1850, 1900, 1800, because $1750 < 1800$.

Therefore, the final lineup is 1750, 1650, 1700, 1850, 1900, 1800.

Xiao A has an ideal lineup in mind and wants to know how many initial lineups can result in that ideal lineup.

Compute the answer modulo $19650827$.

Input Format

The first line contains an integer $n$.
The second line contains $n$ integers, representing Xiao A’s ideal lineup.

Output Format

Output one line with a single integer, which is the value of the answer $\bmod 19650827$.

4
1701 1702 1703 1704

8

Hint

For 30% of the testdata, $n \le 100$.
For 100% of the testdata, $n \le 1000$, $1000 \le h_i \le 2000$.

Translated by ChatGPT 5