Lemper Cooking Competition
Contest: COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2400
Tags: 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:

1. changes the temperature of stove $$$i-1$$$ into $$$A_{i-1} := A_{i-1} + A_{i}$$$,
2. changes the temperature of stove $$$i+1$$$ into $$$A_{i+1} := A_{i+1} + A_{i}$$$, and
3. 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.

Input format:
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 format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
7
2 -1 -1 5 2 -2 9

Example output:
4

Example input:
5
-1 -2 -3 -4 -5

Example output:
-1

Editorial:
Note that an operation is identical to choosing an index $$$p$$$ ($$$1 < p < N$$$) and doing the following things simultaneously:
• Increase $$$A_{p-1}$$$ by $$$A_p$$$.
• Increase $$$A_p$$$ by $$$-2 A_p$$$.
• Increase $$$A_{p+1}$$$ by $$$A_p$$$.
Let's maintain array $$$A$$$ using its prefix sum $$$B_0, B_1, B_2, \ldots, B_N$$$. Formally, define $$$B_i = A_1 + A_2 + \ldots + A_i$$$. In particular, $$$B_0 = 0$$$.
We can see that an operation at index $$$p$$$ changes $$$B$$$ as follows:
• For each index $$$i$$$ such that $$$0 \leq i \leq p-2$$$, $$$B_i$$$ does not change.
• $$$B_{p-1}$$$ increases by $$$A_p$$$. So, $$$B_{p-1}$$$ increases by $$$B_p - B_{p-1}$$$. Therefore, $$$B_{p-1}$$$ changes into $$$B_p$$$.
• $$$B_p$$$ increases by $$$A_p - 2 A_p = -A_p$$$. So, $$$B_p$$$ increases by $$$B_{p-1} - B_p$$$. Therefore, $$$B_p$$$ changes into $$$B_{p-1}$$$.
• For each index $$$i$$$ such that $$$p+1 \leq i \leq N$$$, $$$B_i$$$ increases by $$$A_p - 2 A_p + A_p = 0$$$. So $$$B_i$$$ does not change.
Note that all of the above happen simultaneously. Therefore, an operation at index $$$p$$$ only swaps the values of $$$B_p$$$ and $$$B_{p-1}$$$. So, in one operation, we can swap two adjacent values of $$$B$$$ other than $$$B_0$$$ or $$$B_N$$$.
Making every $$$A_i$$$ non-negative is equivalent to making it such that $$$B_0 \leq B_1 \leq B_2 \leq \ldots \leq B_N$$$. So, if there is a value of $$$B_i$$$ ($$$1 \leq i \leq N-1$$$) such that $$$B_i < B_0$$$ or $$$B_i > B_N$$$, then it is impossible. Otherwise, it is always possible.
To count the number of adjacent swaps to sort $$$B$$$, we can just count the number of inversions in $$$B$$$. This can be done using Fenwick Tree or other methods.
Time complexity: $$$O(N \log N)$$$