D. 【J】T4小清新积木题

有 n 种积木，第 i 种积木有 a_i 个，高 i cm，长宽均 1 cm。

现在所有积木紧贴着排成了一纵列，具体排列方式未知。已知这个纵列的正视图中每一种积木都可以被看见（一个积木在正视图中可见指它前面没有高于或等于它的积木）。求有多少种可能的排列方式，两种排列方式相同当且仅当其侧视图完全重合。

答案可能较大，请使用 long long。

第一行一个正整数 n。

第二行 n 个正整数 a_1,a_2,a_3,\cdots,a_n。

一行一个正整数，表示排列方案数。

样例一中，三种排列方式分别为 {1,2,2,3,3},{1,2,3,2,3},{1,2,3,3,2}，其中每个数列表示三种方案的侧视图中各个位置的高度。

数据说明

• 10pts: 每种积木只有一个
• 20pts: 总方案数小于 10^5
• 20pts: n=2
• 50pts: 无特殊性质

全部数据均满足 n\le 20，每种积木不超过 20 个。

保证答案不超过 10^{15}。