Consider a nondecreasing sequence of integers ~s_1, \dots, s_{n+1}~ (~s_i \le s_{i+1}~ for ~1 \le i \le n~). The sequence ~m_1, \dots, m_n~ defined by ~m_i = \frac{1}{2} (s_i + s_{i+1})~, for ~1 \le i \le n~, is called the mean sequence of sequence ~s_1, \dots, s_{n+1}~. For example, the mean sequence of sequence ~1, 2, 2, 4~ is the sequence ~1.5, 2, 3~. Note that elements of the mean sequence can be fractions. However, this task deals with mean sequences whose elements are integers only.

Given a nondecreasing sequence of ~n~ integers ~m_1, \dots, m_n~, compute the number of nondecreasing sequences of ~n+1~ integers ~s_1, \dots, s_{n+1}~ that have the given sequence ~m_1, \dots, m_n~ as mean sequence.

Task

Write a program that:

• reads from the standard input a nondecreasing sequence of integers,
• calculates the number of nondecreasing sequences, for which the given sequence is mean sequence,
• writes the answer to the standard output.

Input

The first line of the standard input contains one integer ~n~ ~(2 \le n \le 5\,000\,000)~. The remaining ~n~ lines contain the sequence ~m_1, \dots, m_n~. Line ~i+1~ contains a single integer ~m_i~ ~(0 \le m_i \le 1\,000\,000\,000)~. You can assume that in ~50\%~ of the test cases ~n \le 1\,000~ and ~0 \le m_i \le 20\,000~.

Output

Your program should write to the standard output exactly one integer — the number of nondecreasing integer sequences, that have the input sequence as the mean sequence.

Sample Input

3
2
5
9

Sample Output

4

Explanation for Sample Output

Indeed, there are four nondecreasing integer sequences for which ~2,5,9~ is the mean sequence. These sequences are:

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