IndiaHacks Servers

★★★★★

3.7

7 votes

Details

Problem

The INDIA HACKS Organizers has just started the Contest. Initially, they don’t have any Servers. So, they started purchasing new servers to test the programs submitted by Contestant (If you want to be the contestant go to INDIAHACKS-2016).

Meanwhile, program submissions keeps on coming to the website. One server can investigate only one program then it crashes.

If there is Server free (isn't busy with debugging the program) during the submission of a program, it will go un solved.

Given the chronological order of program submissions and server purchases, find the number of programs which will go un solved by the team of INDIAHACKS.

Input The first line of input will contain an integer n (1 ≤ n ≤ 105), the number of events. The next line will contain n space-separated integers.

If the integer is -1 then it means a program has been submitted. Otherwise, the integer will be positive, the number of servers purchases together at that time. No more than 10 servers will be purchased at a time.

Output Print a single integer, the number of programs which will go untreated.

Sample Input

3
3
-1 -1 1
8
1 -1 1 -1 -1 1 1 1
11
-1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1

Sample Output

2
1
8

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Lets consider the second case:

Firstly one server is purchased. Then program comes, the last purchased server will debug this code. One more server is purchased. One more program appears, the last purchased server will investigate this crime. Code submitted. There is no free server at the time, so this program will go untreated. One more server is purchased. One more server is purchased. One more server is purchased. The answer is one, as one program (on step 5) will go untreated.

Contributers:

Anuj Garg