## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Lemper Cooking Competition Codeforces Solution

L. Lemper Cooking Competition
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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\le i\le 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

The first line contains a single integer $N$ ($1\le N\le {10}^{5}$) — the number of stoves.

Solution Click Below:-  👉
👇👇👇👇👇

The second line contains $N$ integers ${A}_{1},{A}_{2},\dots ,{A}_{N}$ ($-{10}^{9}\le {A}_{i}\le {10}^{9}$) — the initial temperatures of the stoves.

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=\left[2,-2,1,4,2,-2,9\right]$.
• Pak Chanek does an operation to stove $2$$A=\left[0,2,-1,4,2,-2,9\right]$.
• Pak Chanek does an operation to stove $3$$A=\left[0,1,1,3,2,-2,9\right]$.
• Pak Chanek does an operation to stove $6$$A=\left[0,1,1,3,0,2,7\right]$.

There is no other sequence of operations such that the number of operations needed is fewer than $4$.