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.


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.


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.


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


Sample Output


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.


There are no comments at the moment.