乌龟 Wilco 想要买一些糖果。为此，他将前往东京的仲见世商店街。

兔子 Tom 是 Wilco 的朋友，他担心 Wilco 吃太多的糖。为了减少 Wilco 能买到的糖果数量，Tom 打算在 Wilco 之前买走一些糖果。

街上有 $N$ 个位置。每个位置要么是一家商店，要么是一个儿童游乐场。相邻位置之间的距离是恒定的。换句话说，这些位置可以看作直线上 $N$ 个等间距的点。

每家商店都有一定数量的糖果（可能为零）。Wilco 将从第一个位置走到最后一个位置，按顺序访问所有位置。每当他到达一家商店时，他都会买下所有可用的糖果并放入他的包中。

兔子 Tom 的移动速度正好是 Wilco 的两倍。与 Wilco 不同，他可以在两个方向上移动。为了不引起怀疑，Tom 一次最多只能携带一颗糖果。一旦他买了一颗糖果，他就会一直携带它，直到把它送给某个游乐场的孩子们。他不能把糖果丢在其他任何地方，但可以在 Wilco 到达终点后将其丢在某个游乐场。Tom 的目标是最小化 Wilco 将要买到的糖果总数。

他们两人都在时间 $0$ 从第一个位置出发。购买和丢弃糖果不需要时间。如果两人在某个时间点位于同一家商店，Tom 可以在 Wilco 之前买走糖果（尽管 Tom 始终最多只能买一颗糖果）。这也意味着，如果第一个位置是一家商店，Tom 可以在时间 $0$ 在 Wilco 之前买走糖果。

假设 Tom 的移动和购买策略是最优的，请问 Wilco 总共会买到多少颗糖果？

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$，描述街上的 $N$ 个位置。

对于每个 $i$，如果 $a_i$ 等于 $-1$，则第 $i$ 个位置是一个游乐场；否则它是一家商店，$a_i$ 指定了其中的糖果数量。商店可能没有糖果（即 $a_i$ 可以为 $0$）。

至少有一个位置是游乐场。

输出格式

输出 Wilco 将买到的糖果总数。

子任务

样例

输入 1

5
-1 1 1 1 1

输出 1

2

说明 1

Tom 前往第二个位置的商店（此时 Wilco 正在第一个和第二个位置之间），他在那里买了一颗糖果并将其带到游乐场。当他到达游乐场时，Wilco 到达了第二个位置。Tom 随后立即前往第三个位置的商店，与 Wilco 同时到达。他买了一颗糖果并将其带回游乐场。此时 Wilco 位于第四个位置，Tom 无法在 Wilco 之前再买到糖果。因此，最终 Wilco 买到了最后两家商店的糖果。

输入 2

8
-1 1 0 0 -1 0 0 3

输出 2

1

说明 2

Tom 在第二个位置买了一颗糖果，并将其带到第五个位置的第二个游乐场。然后他在最后一个位置买了一颗糖果并将其带到第五个位置。此时 Wilco 位于第六个位置。然后他再次前往最后一个位置，并在 Wilco 到达之前赶到。此时 Wilco 位于第七和第八个位置之间。他在那里买了一颗糖果。他无法在买到这颗糖果后及时将其丢弃并买到另一颗，因此 Wilco 能够买到最后一家商店的糖果。

输入 3

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

输出 3

1

说明 3

起初，Tom 和 Wilco 都位于第一个位置，这是一个商店。Tom 在 Wilco 之前买了一颗糖果。接下来，Tom 把那颗糖果丢在第二个位置，然后前往第三个位置，买了一颗糖果并将其带到附近的某个游乐场。然后他及时赶回，在 Wilco 到达第三个位置之前买走了那里的糖果。他将其带到第四个位置的游乐场，然后前往第五个位置并买了一颗糖果。他把那颗糖果丢在附近的某个游乐场，并在 Wilco 到达第五个位置之前及时赶回第五个位置，买走了那里的糖果并将其带到第六个位置的游乐场。他为最后一家商店重复了同样的操作。