题目描述

国王 Dash 需要建造一排总共 $n$ 个房屋，每个房屋的高度 $a_i$ 为一个正整数。

设计师们要求，相邻两座房屋的高度之和必须符合给定的数组 $b$，其中 $b[i] = a[i] + a[i+1]$。你的任务是计算出所有可能的房屋高度组合，使其满足数组 $b$ 的要求。

输入格式

第一行输入一个整数 $n(1\leq n \leq 10^5)$，代表房屋的数量。

第二行输入 $n - 1$ 个整数 $b_i\ (1\le b_i\le 10^9)$，代表设计师要求的数组 $b$。

输出格式

一行一个整数代表所有满足条件的房屋高度组合数量。

样例

4
3 10 12

2

3
2 1

0

4
12 34 236

11