题目描述

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

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

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

输入格式

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

第二行包含 $N - 1$ 个整数，相邻的整数之间使用一个空格分隔，表示连续数组中相邻元素之间的关系，取值只能是 $0$ (表示不连续关系)或 $1$ (表示连续关系)。其中第 $i$ ($1 \leq i \leq 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 \leq N \leq 10$；

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