时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有 \(N\) 个人，第i个人的身高为 \(h_i\)，并且任何两个人的身高都不同，最初他们随意地站成一排队形。

　　现在教练想把队形调整成他心目中的理想队形，调整方式为：整个过程按从左到右的顺序依次把初始队伍中的每个人插入到最终队形中。第一个人直接插入。从第二个人开始的每个人，如果他比前面那个人高，那么将他插入当前队形的最右边；如果他比前面那个人矮，那么将他插入当前队形的最左边。当 \(N\) 个人全部插入后便获得最终的队形。

　　例如，有 6 个人站成的初始队形为：185,190,170,165,180,175，那么教练会按以下步骤获得理想队形：
　　　第1个直接插入队形：**185**
　　　因为190>185，所以第2人插入右边：185, 190
　　　因为170<190，所以第3人插入左边：170, 185, 190
　　　因为165<170，所以第4人插入左边：165, 170, 185, 190
　　　因为180>165，所以第5人插入右边：165, 170, 185, 190, 180
　　　因为175<180，所以第6人插入左边：175, 165, 170, 185, 190, 180
　　因此，最终的队形是175, 165, 170, 185, 190, 180。

　　现在教练心中有一个理想队形，他想知道有多少种初始队形能得到理想队形？

【输入格式】

　　第一行是一个正整数 \(N\)，表示总人数。
　　第二行是 \(N\) 个正整数，\(h_1, h_2, …, h_N\)，表示理想队形中从左到右每个人的身高。

【输出格式】

　　仅包含一个数，表示答案。答案可能很大，只输出 \(mod\0 19650827\) 的值。

【输入输出样例】

　Input

4
170 172 173 174

　Output

32

【样例解释】

　　下面8种初始队形都能得到输入的理想队形：170, 172, 173, 174
　　　{170, 172, 173, 174},
　　　{174, 173, 172, 170},
　　　{172, 170, 173, 174},
　　　{173, 172, 170, 174},
　　　{172, 173, 170, 174},
　　　{172, 173, 174, 170},
　　　{173, 174, 172, 170},
　　　{173, 172, 174, 170}

【数据限制】

　　\(50\%\) 的数据：\(2<=N<=100\)
　　\(100\%\) 的数据：\(1<=N<=1000\)。

【来源】

　Mr.he