Background

Translated from CEOI 2021 Day 2 T2. Tortoise.

Problem Description

Wilco wants to buy candies, so it will visit the Nakamise shopping street.

Tom wants Wilco to eat fewer candies, so it will buy some candies before Wilco does. The shopping street has $N$ equally spaced locations, each of which is either a shop or an empty lot.

Each shop has a certain number of candies (possibly $0$). Wilco will walk from the first location to the last one, visiting all locations in order. Whenever it arrives at a shop, it buys all the candies there. Tom moves at twice Wilco’s speed at any moment and can move in both directions. However, at any moment, Tom can carry at most one candy. Once Tom takes a candy, it will carry it away until it gives it to children playing on an empty lot. Assume that buying candies and giving them away takes no time.

Tom’s goal is to minimize the number of candies Wilco can obtain. Initially, both of them are at the first location, and Tom always moves before Wilco at any moment. That is, if the first location is a shop, Tom can buy one candy before Wilco.

So, with Tom’s interference, how many candies can Wilco get?

Input Format

The first line contains an integer $N$, as described above.

The second line contains $N$ integers $a_1,a_2,\dots,a_N$ describing the $N$ locations on the shopping street. If $a_i=-1$, then the $i$-th location is an empty lot; otherwise, it is a shop selling $a_i$ candies. A shop may have no candies (i.e., $a_i=0$).

It is guaranteed that there is at least one empty lot.

Output Format

Output the number of candies Wilco will buy.

5
-1 1 1 1 1

2

8
-1 1 0 0 -1 0 0 3

1

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

1

Hint

Constraints and conventions

For $100\%$ of the testdata: $1\leq n \leq 5\times 10^5$，$-1\leq a_i \leq 10^4$。

Translated by ChatGPT 5