IOI '05 - Nowy Sacz, Poland

Mean Sequence

Consider a nondecreasing sequence of integers s1,…,sn+1 (sisi+1 for 1 ≤ in). The sequence m1,…,mn defined by mi = ½(si + si+1), for 1 ≤ in, 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 sequences of n+1 integers s1,…,sn+1 that have the given sequence m1,…,mn 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 m1,…,mn. Line i+1 contains a single integer mi (0 ≤ mi ≤ 1 000 000 000). You can assume that in 50% of the test cases n ≤ 1000 and 0 ≤ mi ≤ 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)

I get Memory Limit Exceeded, just by having an array of size 5000001...

In c++ an int takes 4 bytes. Making an array of 5000001 converts into 20000004 bytes. That is around 20 mb. And the limit is 16