[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$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≤𝑖≤𝑁−1$2\le i\le N-1$, then:

1. changes the temperature of stove 𝑖−1$i-1$ into 𝐴𝑖−1:=𝐴𝑖−1+𝐴𝑖$A_{i-1}:=A_{i-1}+A_i$,
2. changes the temperature of stove 𝑖+1$i+1$ into 𝐴𝑖+1:=𝐴𝑖+1+𝐴𝑖$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≤𝑁≤105$1\le N\le {10}^5$) — the number of stoves.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The second line contains 𝑁$N$ integers 𝐴1,𝐴2,…,𝐴𝑁$A_1,A_2,\dots ,A_N$ (−109≤𝐴𝑖≤109$-{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$-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$3$, 𝐴=[2,−2,1,4,2,−2,9]$A=[2,-2,1,4,2,-2,9]$.
• Pak Chanek does an operation to stove 2$2$, 𝐴=[0,2,−1,4,2,−2,9]$A=[0,2,-1,4,2,-2,9]$.
• Pak Chanek does an operation to stove 3$3$, 𝐴=[0,1,1,3,2,−2,9]$A=[0,1,1,3,2,-2,9]$.
• Pak Chanek does an operation to stove 6$6$, 𝐴=[0,1,1,3,0,2,7]$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$4$.