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?
Subtask 1 [10%]
Subtask 2 [30%]
Subtask 3 [30%]
Subtask 4 [30%]
No additional constraints.
The first line contains the integer .
The next line contains space-separated integers , the adjacent sums on the board.
Output the number of arrays of positive integers that could yield . If there is a mistake and no valid array exists, output .
4 5 4 3
The two arrays are
2 3 1 2 and
3 2 2 1.