K. Baby Chaves
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Baby Chaves was playing with his Christmas gift and he got it all messed up, oh no!

His gift was an array of length $$$N$$$ ($$$1\le N\le 10^5$$$) where he can make the following operations: Choose two consecutive numbers in the array, then add $$$k$$$ to one of the numbers and subtract $$$k$$$ from the other one, where $$$k$$$ could be any integer.

Baby Chaves got some of the integers in the array negative, a big mistake as his mom doesn't like negative integers. You don't have much time to fix this before his mom comes home, so tell Baby Chaves what is the minimum number of operations needed to make all the numbers in the array non-negative, that is, greater than or equal to $$$0$$$.

Input

The first line contains $$$N\; (1\le N\le 10^5)$$$ — the length of the array.

The second line contains $$$N$$$ integers $$$a_1, a_2, \dots, a_n\; (-10^9\le a_i \le 10^9)$$$ — the array.

Output

Print $$$-1$$$ if it isn't possible to make all the numbers non-negative; otherwise, print the minimum number of operations needed.

Examples
Input
5
-8 0 15 0 -2
Output
4
Input
5
-10 12 2 -8 2
Output
-1
Input
1
0
Output
0
Note

In the first sample, you could do the following operations:

  • Add $$$8$$$ to the index $$$1$$$ and subtract $$$8$$$ from the index $$$2$$$ to get: $$$[0, -8, 15, 0, -2]$$$.
  • Add $$$8$$$ to the index $$$2$$$ and subtract $$$8$$$ from the index $$$3$$$ to get: $$$[0, 0, 7, 0, -2]$$$.
  • Add $$$2$$$ to the index $$$5$$$ and subtract $$$2$$$ from the index $$$4$$$ to get: $$$[0, 0, 7, -2, 0]$$$.
  • Add $$$2$$$ to the index $$$4$$$ and subtract $$$2$$$ from the index $$$3$$$ to get: $$$[0, 0, 5, 0, 0]$$$.
It can be proven that we need at least $$$4$$$ operations.

In the third sample, the values of the array are already non-negative so you need $$$0$$$ operations.