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.
Output
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.
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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
2 -1 -1 5 2 -2 9
|
4
|
|
2
|
5
-1 -2 -3 -4 -5
|
-1
|