IOI '05 P2 - Mean Sequence

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.5s
Memory limit: 16M

Problem type

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.

Comments

There are no comments at the moment.