P8175 [CEOI 2021] Tortoise

译自 CEOI2021 Day2 T2. [Tortoise](https://hsin.hr/ceoi/competition/ceoi2021_day2_tasks.pdf)。

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 将会买到的糖果数量。

#### 数据范围与约定 对于 $100\%$ 的数据：$1\leq n \leq 5\times 10^5$，$-1\leq a_i \leq 10^4$。 | 子任务 | 分值 | 约束 | | :----: | :--: | :-----------------------------------------------: | | $1$ | $8$ | $1\leq N\leq 20$，$-1\leq a_i\leq 1$ | | $2$ | $10$ | $1\leq N\leq 300$，$-1\leq a_i\leq 1$ | | $3$ | $30$ | $1\leq N\leq 300$，$-1\leq a_i\leq 10^4$ | | $4$ | $25$ | $1\leq N\leq 5\times 10^3$，$-1\leq a_i\leq 10^4$ | | $5$ | $27$ | $1\leq N\leq 5\times 10^5$，$-1\leq a_i\leq 10^4$ |