## DMOPC '21 Contest 9 P1 - Board Numbers

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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

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

#### Input Specification

The first line contains the integer .

The next line contains space-separated integers , the adjacent sums on the board.

#### Output Specification

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

#### Sample Input

4
5 4 3

#### Sample Output

2

#### Explanation

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