P5847 [IOI 2005] mea

考虑一个非递减的整数序列 $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 \le 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$)。

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

**样例说明** 一共存在 $4$ 种序列，它们的平均数序列都是 $2,5,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$。