L. Lemper Cooking Competitiontime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputPak Chanek is participating in a lemper cooking competition. In the competition, Pak Chanek has to cook lempers with N stoves that are arranged sequentially from stove 1 to stove N. Initially, stove i has a temperature of A_i degrees. A stove can have a negative temperature.Pak Chanek realises that, in order for his lempers to be cooked, he needs to keep the temperature of each stove at a non-negative value. To make it happen, Pak Chanek can do zero or more operations. In one operation, Pak Chanek chooses one stove i with 2 \leq i \leq N-1, then:  changes the temperature of stove i-1 into A_{i-1} := A_{i-1} + A_{i},  changes the temperature of stove i+1 into A_{i+1} := A_{i+1} + A_{i}, and  changes the temperature of stove i into A_i := -A_i. Pak Chanek wants to know the minimum number of operations he needs to do such that the temperatures of all stoves are at non-negative values. Help Pak Chanek by telling him the minimum number of operations needed or by reporting if it is not possible to do.InputThe first line contains a single integer N (1 \le N \le 10^5) — the number of stoves.The second line contains N integers A_1, A_2, \ldots, A_N (-10^9 \leq A_i \leq 10^9) — the initial temperatures of the stoves.OutputOutput an integer representing the minimum number of operations needed to make the temperatures of all stoves at non-negative values or output -1 if it is not possible.ExamplesInput
7
2 -1 -1 5 2 -2 9
Output
4
Input
5
-1 -2 -3 -4 -5
Output
-1
NoteFor the first example, a sequence of operations that can be done is as follows:   Pak Chanek does an operation to stove 3, A = [2, -2, 1, 4, 2, -2, 9].  Pak Chanek does an operation to stove 2, A = [0, 2, -1, 4, 2, -2, 9].  Pak Chanek does an operation to stove 3, A = [0, 1, 1, 3, 2, -2, 9].  Pak Chanek does an operation to stove 6, A = [0, 1, 1, 3, 0, 2, 7]. There is no other sequence of operations such that the number of operations needed is fewer than 4.
7
2 -1 -1 5 2 -2 9

4 
['data structures', '*2400']