题目描述

在一首音乐作品中，有一段旋律由 $n$ 个音符组成，每个音符的音高由一个正整数表示。作曲家希望为这段旋律添加一些和声，以产生更加丰富的音乐效果。为了实现这个目标，他们想要找到一组和弦，使得这组和弦的构成方式与旋律的音符间隔完全匹配。

为了帮助作曲家实现这个目标，你需要编写一个程序来计算出可能的音符数组 $a$ 的组合方式数目。给定一个长度为 $n-1$ 的和弦数组 $b$，你的任务是计算出可能的音符数组 $a$ 的组合方式数目。其中，和弦数组 $b$ 中的每个元素 $b[i] = a[i]+ a[i+1]$ 。

作曲家们知道，在音乐中，和弦的构成方式是非常丰富多样的。因此，他们希望通过这个程序来快速地计算出所有可能的音符数组 $a$ 的组合方式数目，以便在创作过程中进行参考。

输入描述

第一行输出为一个整数 $n(1 \leq n \leq 1e5)$ 。

第二行输出为 $n-1$ 个整数，第 $i$ 个整数为 $b_i(1 \leq b_i \leq 1e9)$ 。

输出描述

输出为一个整数，表示数组 $a$ 有多少种可能。

样例1

输入

3
2 2

输出

1

样例解释

$b_1=a_1+a_2=2$

$b_2=a_2+a_3=2$

由于$a_i$均为正整数，因此只有一个方案$[1,1,1]$

样例2

输入

3
2 1

输出

0

样例解释

$b_2=a_2+a_3=1$，由于$a_i$均为正整数，因此没有任何方案可以满足条件。

样例3

输入

4
12 34 236

输出

11