Task: MEA
Mean Sequence
Saturday, 20–08–2005
Available memory: 16 MB. Maximum running time: 5 s.
Consider a nondecreasing sequence of integers s1,...,sn+1 (si ≤si+1 for 1 ≤i ≤n). The sequence m1,...,mn
defined by mi = 1
2(si +si+1), for 1 ≤i ≤n, is called the mean sequence of sequence s1,...,sn+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 m1,...,mn, compute the number of nondecreasing se-
quences of n +1 integers s1,...,sn+1 that have the given sequence m1,...,mn 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.

Example

For the input data:
3
2
5
9
the correct result is:
4
Indeed, there are four nondecreasing integer sequences for which 2,5,9 is the mean sequence. These se-
quences are:
• 2,2,8,10,
• 1,3,7,11,
• 0,4,6,12,
• −1,5,5,13.
v. 1.04
1/1
Mean Sequence

Note (RiseOJ) — The original statement describes file-based input/output; on this judge your program must read from standard input and write to standard output instead.

The first line of the standard input contains one integer n (2 ≤n ≤5000000). The remaining n lines contain
the sequence m1,...,mn. Line i + 1 contains a single integer mi (0 ≤mi ≤1000000000). You can assume
that in 50% of the test cases n ≤1000 and 0 ≤mi ≤20000.

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.

생성자가 기록되지 않았습니다.

출처 IOI 2005