题目描述

题目译自 CEOI 2021 Day2 T2「Tortoise」

乌龟 Wilco 想要买些糖。为了买糖，他会去东京的仲见世商店街。

野兔 Tom 是 Wilco 的朋友，他担心 Wilco 吃糖吃得太多。为了减少 Wilco 可以买到的糖的数量，Tom 打算在他之前买一些糖。

商店街有 $N$ 个地点，要么是一间店铺，要么是一个给孩子的游乐场。相邻两个地点间的距离是一个常数。换句话说，这些地点可以看成在一条线上等间距分布的 $N$ 个点。

每个商店有一些数量的糖果（可能为 $0$）。Wilco 会从第一个地点开始，按顺序依次经过所有地点，最后走到最后一个地点。每次到达一间店铺，他就会买下店内所有的糖果，并且把它们放在包里。

Tom 恰好比 Wilco 移动快两倍。和 Wilco 不同的是，他可以双向移动。为了避免被 Wilco 怀疑，Tom 一次最多只能携带一块糖。每当他买了一块糖，他就会一直携带者它，直到把这块糖送给游乐场中的孩子们。他不能把糖丢在别的地方，但是可以在 Wilco 走到最后一个地点后丢在某个游乐场中。Tom 的目标是最小化 Wilco 会买下的糖果个数。

他们两个都在时刻 $0$ 从第一个地点出发。买和送出糖果不花费时间。如果在某时他们两个都在同一家商店，Tom 可以在 Wilco 之前买糖（尽管 Tom 总是只能买至多一个糖果）。这也一位置如果第一个地点是商店的话，Tom 可以在时刻 $0$ 时在 Wilco 之前买糖。

假设 Tom 的移动和购买策略都是最优的，Wilco 会买到多少糖？

输入格式

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

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$，描述街上的 $N$ 个地点。

对于每个 $i$，如果 $a_i$ 等于 $-1$，那么第 $i$ 个地点是一个游乐场，否则它是一家商店，$a_i$ 表示店内所买糖的数量。店里可能没有糖（即，$a_i$ 可能等于 $0$）。

至少有一个地点是游乐场。

输出格式

输出 Wilco 会买糖的数量。

5
-1 1 1 1 1

2

Tom 去第二个地点上的商店（在这时 Wilco 正好在一二两地点之间），他会买一块糖，并把它带到游乐场。当他到达游乐场时，Wilco 恰好到了第二个地点。接着 Tom 立刻出发到第三个地点上的商店处，他和 Wilco 同时到达。他会买下一块糖并把它带到游乐场。在此时 Wilco 到了第四个地点，并且 Tom 没办法再在 Wilco 之前买到更多的糖了。所以最后 Wilco 会在最后两家商店买到糖。

8
-1 1 0 0 -1 0 0 3

1

Tom 会第二个位置上的商店买一块糖，并把它带到第五个地点上的游乐场。然后他会在最后一个地点买一块糖，并把它带到第五个地点。在此时 Wilco 在第六个地点。Tom 会再次去最后一个地点，并且恰好在 Wilco 之前到达那里。此时 Wilco 在第七八个地点之间。Tom 会在那里买一块糖。但他不能丢掉这块糖然后再买一块，因此 Wilco 可以在最后一个位置买到一块糖。

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

1

开始时，Tom 和 Wilco 在第一个位置，而第一个位置是一家商店。Tom 在 Wilco 之前买一块糖。接下来，Tom 会在第二个地点送出这块糖，然后前往第三个位置，买一块糖并带到附近的两个游乐场之一送出。然后他会回到第三个位置，这时恰好 Wilco 也到了第三个位置，所以 Tom 可以在 Wilco 之前买到这块糖。他会吧糖带到第四个位置，然后前往第五个位置买一块糖。他会把糖带到附近的两个游乐场之一送出，然后回到第五个位置。此时 Wilco 也刚刚到达第五个位置，所以 Tom 可以买到另一块糖，并把它带到第六个位置处的游乐场。对于最后一间商店他会重复相同的操作。

数据范围与提示