考虑一个非降整数序列 $s_1, \dots, s_{n+1}$（对于 $1 \le i \le n$，满足 $s_i \le s_{i+1}$）。由 $m_i = \frac{1}{2}(s_i + s_{i+1})$（对于 $1 \le i \le n$）定义的序列 $m_1, \dots, m_n$ 被称为序列 $s_1, \dots, s_{n+1}$ 的均值序列。例如，序列 $1, 2, 2, 4$ 的均值序列是 $1.5, 2, 3$。请注意，均值序列的元素可以是分数。然而，本题仅讨论元素均为整数的均值序列。

给定一个由 $n$ 个整数组成的非降序列 $m_1, \dots, m_n$，计算有多少个由 $n+1$ 个整数组成的非降序列 $s_1, \dots, s_{n+1}$，其均值序列为给定的序列 $m_1, \dots, m_n$。

任务

编写一个程序：

• 从标准输入读取一个非降整数序列，
• 计算以该给定序列作为均值序列的非降序列的数量，
• 将答案输出到标准输出。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 5\,000\,000$）。

接下来的 $n$ 行包含序列 $m_1, \dots, m_n$。第 $i+1$ 行包含一个整数 $m_i$（$0 \le m_i \le 1\,000\,000\,000$）。

你可以认为在 50% 的测试用例中，$n \le 1000$ 且 $0 \le m_i \le 20\,000$。

输出格式

输出到标准输出，包含唯一的一个整数——以输入序列作为均值序列的非降整数序列的数量。

样例

输入样例 1

3
2
5
9

输出样例 1

4

说明

事实上，共有四个非降整数序列以 $2, 5, 9$ 作为均值序列。这些序列是：

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