题目描述

考虑一个非递减的整数序列 $S_1,\cdots,S_{n+1}$ ($S_i \le S{i+1}$，$1 \le i \le n$)。 序列 $M_1 \cdots M_n$ 是定义在序列 $S$ 的基础上，关系式为 $M_i = \frac{S_i + S_{i+1}}{2 }$（$1 \le i < n$）, 序列 $M$ 叫做序列 $S$ 的平均数序列。

例如序列 $1,2,2,4$ 的平均数序列为 $1.5,2,3$. 注意到平均数序列中的元素可能为小数。但是本题的任务只是处理平均数序列都为整数的情况。

给出一个 $n$ 个数字的非递减的整数序列 $M_1,M_2,\cdots,M_n$。请你计算出：序列 $S_1,\cdots,S_{n+1}$ 的平均序列是 $M_1,\cdots,M_n$。 求满足以上条件的序列 $S$ 的总个数。

任务：从标准输入文件中读入一个非递减的整数序列。计算出平均序列是给出序列的整数序列的总个数。把计算结果写到标准输出文件中。

输入格式

输入文件的第一行包含一个整数 $n$ （$2 \le n \le 5 \times 10^6$）。

接下来的 $n$ 行包含了这个给出的整数序列 $M_1,\cdots,M_n$。第 $i+1$ 行包含一个整数 $M_i$ ( $1 \le m_i \le 10^9$)。

输出格式

输出文件仅一行，即所求答案。

3
2
5
9

4

提示

样例说明

一共存在 $4$ 种序列，它们的平均数序列都是 $2,3,9$。这四种序列如下：

• $2,2,8,10$
• $1,3,7,11$
• $0,4,6,12$
• $-1,5,5,13$

数据范围

对于 $50\%$ 的数据，$2 \le n \le 1000$，$1 \le M_i \le 2 \times 10^4$；

对于 $100\%$ 的数据，$2 \le n \le 5 \times 10^6$，$1 \le M_i \le 10^9$。