L. Lemper Cooking Competition
data structures
Pak 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.
The 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.
Output 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.
For 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\).