Problem Description

Wilco wants to buy candies, and for that, it will visit Nakamise shopping street.

Tom wants Wilco to eat fewer candies, and for that, it will buy some candies ahead of Wilco. There are $N$ equally spaced locations on the shopping street, which are either stores or empty spaces.

Each store has a certain number of candies (possibly $0$). Wilco will walk from the first location to the last, visiting all locations in order. Whenever it reaches a store, it will buy all the candies. Tom moves at twice the speed of Wilco and can move in both directions. However, Tom can carry at most one candy at a time. Once Tom gets a candy, it will carry it until it gives it to a child playing in an empty space. Assume that buying and giving away candies do not take any time.

Tom's goal is to minimize the number of candies Wilco can get. Initially, both are at the first location, and Tom moves any time before Wilco. That is, if the first location is a store, Tom can buy a candy before Wilco.

How many candies can Wilco get under Tom's interference?

Input Format

The first line of input contains an integer $N$, as described in the problem.

The second line contains $N$ integers $a_1, a_2, \dots, a_N$, representing the $N$ locations on the shopping street. If $a_i = -1$, the $i$-th location is an empty space; otherwise, it is a store selling $a_i$ candies. It is possible for a store to have no candies (i.e., $a_i = 0$).

It is guaranteed that at least one location is an empty space.

Output Format

Output the number of candies Wilco will buy.

Sample Input and Output

Sample Input #1

5
-1 1 1 1 1

Sample Output #1

2

Sample Input #2

8
-1 1 0 0 -1 0 0 3

Sample Output #2

1

Sample Input #3

8
2 -1 2 -1 2 -1 2 -1

Sample Output #3

1

Notes/Hints

Data Range and Constraints

For $100\%$ of the data: $1 \leq N \leq 5 \times 10^5$, $-1 \leq a_i \leq 10^4$.

见题面 Input 部分

见题面 Output 部分