题目描述

题目译自 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

8
-1 1 0 0 -1 0 0 3

1

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

1

数据范围与提示