P3205 [HNOI2010] Choir

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. - 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$.

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

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

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