描述 Description

有一个非递减的整数序列S1，S2，S3，……，S(n+1)（Si<=S(i+1)）。定义序列m1，m2，…，mn为S的“M序列”，其中mi=(Si+S(i+1))/2。

例如，S=(1, 3, 3, 5)，则m=(2, 3, 4)。

现在给你序列m，要你求有多少个S序列的“M序列”是序列m。

输入格式 Input Format

第一行一个整数n，

下接n行，每行一个整数mi

输出格式 Output Format

一个整数，表示有多少个S序列的“M序列”是序列m

样例输入 Sample Input

3
2
5
9

样例输出 Sample Output

4

时间限制 Time Limitation

各数据均为2秒

注释 Hint

样例说明：存在如下四个数列S满足要求：

2，2，8，10；
1，3，7，11；
0，4，6，12；
-1，5，5，13。

数据范围

50%的数据n<=1000，mi<=20000

100%的数据2<=n<=100000，mi<=10^9.