在奇境（Wonderland）的华尔街上，有 $n$ 家银行，其中 $10000 > n > 0$。每家银行恰好有两个邻居，即左邻居（$L$）和右邻居（$R$）。第一家银行的左邻居是最后一家银行，而最后一家银行的右邻居是第一家银行。每家银行 $i$（$n > i \ge 0$）的资金为 $k_i$，满足 $32000 > k_i > -32000$。已知所有银行的资金总和为正数。

每当某家银行 $i$ 的资金 $k_i$ 为负数时，银行仙子（Bank Fairy）可以进行一次魔法操作，将该资金变为正数。例如，如果 $k_i = -7$，在魔法操作后，$k_i = 7$。不幸的是，魔法操作会对银行 $i$ 的两个邻居产生影响：它们的资金都会减少，减少的量等于银行 $i$ 操作前资金的绝对值。例如，如果银行 $L$ 的资金为 $k_L = 5$，银行 $R$ 的资金为 $k_R = 11$，那么在对银行 $i$ 进行魔法操作后，它们的资金将分别变为 $k_L = -2$ 和 $k_R = 4$。

要使所有银行的资金都大于或等于 $0$，银行仙子最少需要进行多少次魔法操作？

输入格式

第一行包含一个整数 $n$，表示银行的数量。

第二行包含所有银行的资金 $k_i$（$n > i \ge 0$），按照它们在奇境华尔街上的排列顺序给出。每个资金值之间用单个空格分隔，最后一个资金值后面直接跟换行符。

输出格式

输出仅一行，包含一个整数，表示最少需要的魔法操作次数。

样例

输入样例 1

4
1 -2 -1 3

输出样例 1

9