Down the Pyramid

Interview

Time limit2sMemory limit512 MB

Summary

Count non-negative integer sequences of length n+1 lying under a given length-n sequence, where each adjacent pair sums to the number above it.

Level: Medium6 of 10
Topics: Math, Implementation, Array, Brute force
Solved: No attempts yet

Problem

Do you like number pyramids? Given a sequence that represents the base, you usually build the rest of the pyramid bottom-up: for each pair of adjacent numbers, you compute their sum and write it above them. For example, given the base sequence [1, 2, 3], the sequence directly above it is [3, 5], and the top of the pyramid is [8].

However, I am not interested in completing the pyramid. I would much rather go underground. So for a sequence of n non-negative integers, I will write a sequence of n + 1 non-negative integers below it such that each number in the original sequence is the sum of the two numbers I put below it. There may be several possible sequences, or perhaps none at all. Could you tell me how many sequences there are to choose from?

Input

The input consists of:

one line with the integer n (1 ≤ n ≤ 106), the length of the base sequence.
one line with n integers a1, . . . , an (0 ≤ ai ≤ 108 for each i), forming the base sequence.

Output

Output a single integer, the number of non-negative integer sequences that would have the input sequence as the next level in a number pyramid.

Examples2

Example 1
Input
```
6
12 5 7 7 8 4
```
Expected output
```
2
```
Example 2
Input
```
3
10 1000 100
```
Expected output
```
0
```