1295. [HNOI 2010] 合唱队

【题目描述】

为了在即将到来的晚会上有更好的演出效果，作为$ AAA $合唱队负责人的小$ A $需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共有$ N $个人，第$ i $个人的身高为$ H_i $毫米$ (1000≤Hi≤2000) $，并且已知任何两个人的身高都不同。假定最终排出的队形是$ N $个人站成一排，为了简化问题，小$ A $想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终排出的队形中：

• 第一个人直接插入空的当前队形中。

• 对从第二个人开始的每个人，

1、 如果他比前面那个人高($ H $较大)，那么将他插入当前队形的最右边。

2、 如果他比前面那个人矮($ H $较小)，那么将他插入当前队形的最左边。

当$ N $个人全部插入当前队形后便获得最终排出的队形。 例如，有 6 个人站成一个初始队形，身高依次为1850、1900、1700、1650、1800和1750，那么小$ A $会按以下步骤获得最终排出的队形：

• 1850

• 1850, 1900 因为 1900 > 1850

• 1700, 1850, 1900 因为 1700 < 1900

• 1650, 1700, 1850, 1900 因为 1650 < 1700

• 1650, 1700, 1850, 1900, 1800 因为 1800 > 1650

• 1750, 1650, 1700, 1850, 1900, 1800 因为 1750 < 1800

因此，最终排出的队形是1750, 1650, 1700, 1850, 1900, 1800。

小$ A $心中有一个理想队形，他想知道从多少种初始队形出发能通过上述排队的方式获得他心中的理想队形作为最终排出的队形？

【输入格式】

从文件$ i $中读入数据，输入文件第一行是一个正整数$ N $，表示总人数。输入文件第二行是用空格隔开的$ N $个正整数，从左到右表示小$ A $心中的理想队形：$ H_1 , H_2,..., H_N $。输入的数据保证$ 1000 ≤ H_i ≤ 2000 $且没有相同的$ H $值，其中$ 30\% $的数据满足$ 1 ≤ N ≤ 100 $，$ 100\% $的数据满足$ 1 ≤ N ≤ 1000 $。

【输出格式】

输出文件output.txt仅包含一个数，表示从多少种初始队形出发能通过上述排队的方式获得输入文件中指定的小$ A $心中的理想队形。因为满足条件的初始队形数可能很大，所以规定只要输出满足条件的初始队形数$ mod 19650827 $的值。

【样例输入1】

4
1701 1702 1703 1704

【样例输出1】

8

【样例输入2】

4
1704 1703 1702 1701

【样例输出2】

0

【提示】

样例 1 解释：

8种初始队形分别为 (1701, 1702, 1703, 1704), (1704, 1703, 1702, 1701), (1702, 1701, 1703, 1704), (1703, 1702, 1701, 1704), (1702, 1703, 1701, 1704), (1702, 1703, 1704, 1701), (1703, 1704, 1702, 1701), (1703, 1702, 1704, 1701).