题目背景

译自 CEOI2021 Day2 T2. Tortoise。

题目描述

Wilco 想购买糖果，为此它将访问 Nakamise 商店街。

Tom 想让 Wilco 少吃点糖果，为此它将在 Wilco 前购买一些糖果。商店街上共有 $N$ 个等距离的地点，它们要么是商店要么是空地。

每家商店都有一定数量的糖果（可能为 $0$） Wilco 将会从第一个地点走到最后一个，顺序访问所有地点。每当它到达一家商店时它会买走所有糖果。Tom 每一刻的移动速度是 Wilco 的两倍，且可以朝两个方向移动。但是，Tom 每一刻只能携带最多一颗糖果。一旦 Tom 拿到一颗糖果，它就会把它带走直到把它交给在空地上玩的小孩。假设购买和给出糖果均不消耗时间。

Tom 的目标是最小化 Wilco 能拿到的糖果。初始时它们均在第一个地点，Tom 任何时刻先于 Wilco 行动。即如果第一个地点是商店，Tom 可以先于 Wilco 购买一颗糖果。

那么在 Tom 的干扰下 Wilco 能拿到多少糖果呢？

输入格式

输入的第一行包含一个整数 $N$，含义如题目描述。

第二行有 $N$ 个整数 $a_1,a_2,\dots,a_N$ 表示商店街上的 $N$ 个地点，其中 $a_i=-1$ 时第 $i$ 个地点为空地，否则它为商店且有 $a_i$ 颗糖果出售。有可能一家商店没有糖果（即 $a_i=0$）

保证至少有一个地点是空地。

输出格式

输出 Wilco 将会买到的糖果数量。

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

提示

数据范围与约定

对于 $100\%$ 的数据：$1\leq n \leq 5\times 10^5$，$-1\leq a_i \leq 10^4$。