Description

在炉石传说中，对于每一位选手有一排位置 $1,2,...,n$。每个位置要么放着一个障碍物，要么放着一个随从。用数组 $a_1,a_2...a_n$ 给出场面：

若 $a_i = -1$，表示位置 $i$ 放着障碍物（阻断伤害传播）；

若 $a_i > 0$，表示位置 $i$ 放着一个随从，生命值为 $a_i$。

炉石传说自残术这套卡组中通常会带有一张牌叫做多米诺效应。

你现在手里有无限张法术牌 "多米诺效应"。每使用一张牌，你选择一个场上的随从位置 $s$（必须选随从而非障碍）并选择方向（向左或向右）。法术效果如下：

对被选位置 $s$ 自身造成 $2$ 点伤害；

沿所选方向对该方向上连续的随从依次造成递增伤害：下一个随从受到 $3$，再下一个受到 $4$，以此类推；

如果遇到 障碍物 或 达到阵列边界，传播停止；

重要：即便某个随从的生命值降到 $\leq 0$，它也不会从场上消失，之后仍会被后续法术继续命中（只是生命可以为负）。

现在你需要求出清除所有障碍物需要使用的最小牌数。

Format

Input

第一行：整数 $n$，其中$1 ≤ n ≤ 1000$。

第二行：$n$ 个整数 $a_1 a_2 ... a_n$ （每个 $a_i = -1$ 或 $1 ≤ a_i ≤ 10000$）。

Output

输出一行，输出清除障碍物的最小牌数。

Samples

4
2 3 4 5

1

Limitation

1s, 1024KiB for each test case.