问题描述

小蓝对连续数组很感兴趣，对于一个长度为 $N$ 的连续数组 $nums$，$nums$ 中的元素取值范围为 $1∼N$，且 $nums$ 中不存在重复元素，每两个相邻的数组元素 $nums[i]$、$nums[i+1]$ 之间都存在关系$(1≤i≤N−1)$，且只可能是以下两种关系中的一种:

• 连续，此时 $nums[i+1]$ 等于 $nums[i]+1$;
• 不连续，此时 $nums[i+1]$ 不等于 $nums[i]+1$。

现在给出一个长度为 $N$ 的数组中任意相邻的数组元素之间的关系，请问共有多少种满足条件的连续数组?

输入格式

输入的第一行包含一个整数 $N$ 表示数组长度。

第二行包含 $N−1$ 个整数，相邻的整数之间使用一个空格分隔，表示连续数组中相邻元素之间的关系，取值只能是 $0$ (表示不连续关系)或 $1$ (表示连续关系)。其中第 $i(1≤i≤N−1)$ 个整数表示 $nums[i]$ 和 $nums[i+1]$ 之间的关系。

输出格式

输出一行包含一个整数表示答案。

样例

5
0 0 1 1

3

样例说明

符合条件的连续数组有：$[1,5,2,3,4]$、$[2,1,3,4,5]$、$[5,4,1,2,3]$。

评测用例规模与约定

对于 $30\%$ 的评测用例，$1≤N≤10$；

对于所有评测用例，$1≤N≤15$。