Description

Consider a non-decreasing integer sequence $S_1,\cdots,S_{n+1}$ ($S_i \le S_{i+1}$, $1 \le i \le n$). A sequence $M_1 \cdots M_n$ is defined based on the sequence $S$ by the relation $M_i = \frac{S_i + S_{i+1}}{2}$ ($1 \le i \le n$). The sequence $M$ is called the mean sequence of $S$.

For example, the mean sequence of $1,2,2,4$ is $1.5,2,3$. Note that elements in the mean sequence may be decimals. However, in this problem, you only need to handle the case where all elements of the mean sequence are integers.

You are given a non-decreasing integer sequence $M_1,M_2,\cdots,M_n$ of length $n$. Please compute the total number of sequences $S_1,\cdots,S_{n+1}$ such that the mean sequence of $S$ is exactly $M_1,\cdots,M_n$.

Task: Read a non-decreasing integer sequence from standard input. Compute the number of integer sequences whose mean sequence equals the given integer sequence. Write the result to standard output.

Input Format

The first line contains an integer $n$ ($2 \le n \le 5 \times 10^6$).

The next $n$ lines contain the given integer sequence $M_1,\cdots,M_n$. The $(i+1)$-th line contains an integer $M_i$ ($1 \le M_i \le 10^9$).

Output Format

Output only one line, which is the required answer.

3
2
5
9

4

Hint

Sample Explanation

There are $4$ sequences in total whose mean sequence is $2,5,9$. These four sequences are:

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

Constraints

For $50\%$ of the testdata, $2 \le n \le 1000$, $1 \le M_i \le 2 \times 10^4$.

For $100\%$ of the testdata, $2 \le n \le 5 \times 10^6$, $1 \le M_i \le 10^9$.

Translated by ChatGPT 5