### IOI '05 - Nowy Sacz, Poland

## Mean Sequence

Consider a nondecreasing sequence of integers *s*_{1},…,*s*_{n+1}
(*s*_{i} ≤ *s*_{i+1} for
1 ≤ *i* ≤ *n*). The sequence *m*_{1},…,*m*_{n} defined by *m*_{i} =
½(*s*_{i} + *s*_{i+1}), for
1 ≤ *i* ≤ *n*, is called the mean sequence of sequence *s*_{1},…,*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},…,*m*_{n}, compute the
number of nondecreasing sequences of *n*+1 integers *s*_{1},…,*s*_{n+1} that have
the given sequence *m*_{1},…,*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.

### Input

The first line of the standard input contains one integer*n*(2 ≤

*n*≤ 5 000 000). The remaining

*n*lines contain the sequence

*m*

_{1},…,

*m*

_{n}. Line

*i*+1 contains a single integer

*m*

_{i}(0 ≤

*m*

_{i}≤ 1 000 000 000). You can assume that in 50% of the test cases

*n*≤ 1000 and 0 ≤

*m*

_{i}≤ 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

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

All Submissions

Best Solutions

**Point Value:** 12 (partial)

**Time Limit:** 5.00s

**Memory Limit:** 16M

**Added:** Aug 27, 2009

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...