DMOPC '21 Contest 9 P1 - Board Numbers - Olympiads Online Judge

DMOPC '21 Contest 9 P1 - Board Numbers

Points: 7 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

You wrote your favourite $N$ ~N~ positive integers on the board and then wrote the $N-1$ ~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$ ~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$ ~2 \le N \le 10^6~

$1 \le a_i \le 10^9$ ~1 \le a_i \le 10^9~

Subtask 1 [10%]

$N = 2$ ~N = 2~

Subtask 2 [30%]

$N = 3$ ~N = 3~

Subtask 3 [30%]

$1 \le a_i \le 10$ ~1 \le a_i \le 10~

Subtask 4 [30%]

No additional constraints.

Input Specification

The first line contains the integer $N$ ~N~.

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

Output Specification

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

Sample Input

4
5 4 3

Sample Output

Explanation

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

Comments

1
Nick_Lomov commented on Oct. 31, 2024, 7:24 p.m.
For those unsure what adjacent sums mean, here's an example:

Original array: 1 2 3 4 Adjacent sums array: 3 5 7

So 3=1+2, 5=2+3, etc.

In this problem, you're given the adjacent sums array and have to figure out the number of possibilities for the original array.