Wilco's Candy Purchase Under Tom's Interference

Wilco is on a mission to buy candy along Nakamise street. The street has N positions equally spaced along a line. Each position is either a shop or an empty space. If the position is a shop, it has a non‐negative number of candies (possibly 0). If the position is empty, it is represented by -1 in the input.

Wilco starts at position 1 at time 0 and visits each location in increasing order (so that he reaches position i at time i-1). At every shop he visits, Wilco buys all the candies available at that shop.

Tom, however, wants Wilco to have less candy. At the start (position 1, time 0) Tom is also present and may act before Wilco at each location. Tom moves with speed exactly twice that of Wilco and is allowed to move in both directions. However, at any moment Tom can carry at most one candy. His strategy is as follows: whenever he can, Tom intercepts a shop by picking up one candy (if the shop has at least one candy) before Wilco arrives. But once Tom picks a candy from a shop, he must deliver it immediately to a little kid who is playing at an empty space. Delivering (i.e. giving away) the candy does not consume extra time, but while Tom is carrying a candy, he is occupied and cannot intercept another shop. Moreover, Tom cannot pick more than one candy from any shop even if that shop has several; he can only intercept one candy per shop.

Assume that Tom always plans his moves optimally in order to minimize the total number of candies Wilco ultimately collects. In particular, Tom can intercept at most one candy per pair of a shop and a subsequent empty space. (Note that if a shop has 0 candies then intercepting is pointless.)

If we denote by \(C_i\) the number of candies at the i^th position (when it is a shop) and define the total candy Wilco would normally collect as \(\sum C_i\), then under Tom's interference, Wilco collects

[ \text{Answer} = \sum_{\text{shops}} C_i - (\text{maximum number of interceptions}) ]

Your task is to compute the final number of candies Wilco will have, given the layout of the street.

Note: Tom can only intercept a shop if there exists an empty space (with index greater than that of the shop) where he can deliver the intercepted candy. After delivering the candy at an empty space, Tom becomes free and resumes his quest. In particular, after each interception the effective state of Tom is reset to that empty space.

Input/Output timing details: The movement times due to the speeds are already ensured by the condition that Tom’s speed is double of Wilco’s. Thus, under optimal play, the only constraint that matters is the ordering: a shop can be intercepted only if there is an empty space later than it, and interceptions are chained in increasing order of positions.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(N\) (\(1 \le N \le 10^5\)), the number of positions on the street.
• The second line contains \(N\) space‐separated integers. For each position, a nonnegative integer represents a shop (and indicates the number of candies at that shop) while -1 indicates an empty space.

Note: Position 1 is the starting point for both Wilco and Tom. If position 1 is a shop, Tom may intercept its candy before Wilco buys any.

outputFormat

Output a single integer: the total number of candies Wilco collects after Tom’s optimal interference.

sample

5
5 -1 3 -1 7

13