Problem G: 核心法阵

小 X 正在制作一件魂导器，而魂导器中最重要的部分则是它的核心法阵。
一件核心法阵由 N 个互不相同的符号按一定的顺序排成一列组成，按照魔力等级，我们依次将它们标号为 1~N，在一件有效的核心法阵中，每个符号恰好出现一次，显然，一件有效的核心法阵长度为 N。例如(2,1,3)是一件有效的核心法阵，而(2,2,2)则不是，因为 2 出现了 3 次，而 1 和 3 都没有出现。
我们称一件有效的核心法阵的第 L 位到第 R 位是连续的，当且仅当核心法阵的这一段符号在数值上也是连续的。例如核心法阵(1,3,2,4,5)中，连续的位置有第 1 位到第 1 位、第 2 位到第 2 位、第 3 位到第 3 位、第 4 位到第 4 位、第 5位到第 5 位、第 2 位到第 3 位、第 4 位到第 5 位、第 1 位到第 3 位、第 2 位到第 4 位、第 1 位到第 4 位、第 2 位到第 5 位、第 1 位到第 5 位。
现在小 X 想要制作这样一件核心法阵，使得它以第 i 位结尾的最长的连续段长度为 Ai，一共有多少种不同的核心法阵满足小 X 的要求呢？

【样例 1 输入】
3
1 1 3
【样例 1 输出】
2
【样例 2 输入】
5
1 1 3 4 5
【样例 2 输出】
8
【样例解释】
在样例 1 中，满足小 X 的要求的核心法阵分别是(1,3,2),(3,1,2)。
在样例 2 中，满足小 X 的要求的核心法阵分别是(1,3,2,4,5),(2,4,3,1,5), (2,4,3,5,1),(3,1,2,4,5),(3,5,4,2,1),(4,2,3,1,5),(4,2,3,5,1),(5,3,4,2,1)。
【数据范围及子任务】
各有 10%的数据满足 N=1,2,3,4,5,6,7,8,9,10。
对于 40%的数据，N≤4，Ai=i。
对于 100%的数据，N≤10，1≤Ai≤i，至少存在一个符合条件的核心法阵。