P3288 - [HNOI2010] 合唱队 - JOYSKID
题目描述
为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 lns="http://www.w3.org/1998/Math/MathML">�n 个人，第 lns="http://www.w3.org/1998/Math/MathML">�i 个人的身高为 lns="http://www.w3.org/1998/Math/MathML">ℎ�hi 米（lns="http://www.w3.org/1998/Math/MathML">1000≤ℎ�≤20001000≤hi≤2000），并已知任何两个人的身高都不同。假定最终排出的队形是 lns="http://www.w3.org/1998/Math/MathML">�A 个人站成一排，为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终棑排出的队形中：
第一个人直接插入空的当前队形中。
对从第二个人开始的每个人，如果他比前面那个人高（lns="http://www.w3.org/1998/Math/MathML">ℎh 较大），那么将他插入当前队形的最右边。如果他比前面那个人矮（lns="http://www.w3.org/1998/Math/MathML">ℎh 较小），那么将他插入当前队形的最左边。
当 lns="http://www.w3.org/1998/Math/MathML">�n 个人全部插入当前队形后便获得最终排出的队形。
例如，有 lns="http://www.w3.org/1998/Math/MathML">66 个人站成一个初始队形，身高依次为 lns="http://www.w3.org/1998/Math/MathML">1850,1900,1700,1650,1800,17501850,1900,1700,1650,1800,1750，
那么小 A 会按以下步骤获得最终排出的队形：
lns="http://www.w3.org/1998/Math/MathML">18501850。
lns="http://www.w3.org/1998/Math/MathML">1850,19001850,1900，因为 lns="http://www.w3.org/1998/Math/MathML">1900>18501900>1850。
lns="http://www.w3.org/1998/Math/MathML">1700,1850,19001700,1850,1900，因为 lns="http://www.w3.org/1998/Math/MathML">1700<19001700<1900。
lns="http://www.w3.org/1998/Math/MathML">1650,1700,1850,19001650,1700,1850,1900，因为 lns="http://www.w3.org/1998/Math/MathML">1650<17001650<1700。
lns="http://www.w3.org/1998/Math/MathML">1650,1700,1850,1900,18001650,1700,1850,1900,1800，因为 lns="http://www.w3.org/1998/Math/MathML">1800>16501800>1650。
lns="http://www.w3.org/1998/Math/MathML">1750,1650,1700,1850,1900,18001750,1650,1700,1850,1900,1800，因为 lns="http://www.w3.org/1998/Math/MathML">1750<18001750<1800。
因此，最终排出的队形是 lns="http://www.w3.org/1998/Math/MathML">1750,1650,1700,1850,1900,18001750,1650,1700,1850,1900,1800。
小 A 心中有一个理想队形，他想知道多少种初始队形可以获得理想的队形。
请求出答案对 lns="http://www.w3.org/1998/Math/MathML">1965082719650827 取模的值。
输入格式
第一行一个整数 lns="http://www.w3.org/1998/Math/MathML">�n。 第二行 lns="http://www.w3.org/1998/Math/MathML">�n 个整数，表示小 A 心中的理想队形。
输出格式
输出一行一个整数，表示答案 lns="http://www.w3.org/1998/Math/MathML"> mod 19650827mod19650827 的值。
4
1701 1702 1703 1704
8