题目描述

乌龟 $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$ 会买糖的数量。

---

样例 1
输入

5
-1 1 1 1 1

输出

2

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

---

样例 2
输入

8
-1 1 0 0 -1 0 0 3

输出

1

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

---

样例 3
输入

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

输出

1

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

---

数据范围与提示

子任务编号	附加限制	分值
1	$1\le N\le 20$, $\lvert a_i\lvert\le 1$	8
2	$1\le N\le 300$, $\lvert a_i\lvert\le 1$	10
3	$1\le N\le 300$,$-1\le a_i\le 10^4$	30
4	$1\le N\le 5\times 10^3$,$-1\le a_i\le 10^4$	25
5	$1\le N\le 5\times 10^5$,$-1\le a_i\le 10^4$	27