You wrote your favourite ~N~ positive integers on the board and then wrote the ~N-1~ adjacent sums too. Someone erased your integers, but not your sums. Instead of being mad, you became quite curious: how many arrays of ~N~ numbers could generate these sums?

That is, given an array of adjacent sums, how many arrays of positive integers generate these sums?

Constraints

~2 \le N \le 10^6~

~1 \le a_i \le 10^9~

Subtask 1 [10%]

~N = 2~

Subtask 2 [30%]

~N = 3~

Subtask 3 [30%]

~1 \le a_i \le 10~

Subtask 4 [30%]

No additional constraints.

Input Specification

The first line contains the integer ~N~.

The next line contains ~N - 1~ space-separated integers ~a_i~, the adjacent sums on the board.

Output Specification

Output the number of arrays of positive integers that could yield ~a_i~. If there is a mistake and no valid array exists, output ~0~.

Sample Input

4
5 4 3

Sample Output

2

Explanation

The two arrays are 2 3 1 2 and 3 2 2 1.