Faraz 参加了一个游戏，但他对这个游戏没什么兴趣。游戏规则如下：Faraz 有两个序列 $a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, b_n$。所有的 $a_i$ 均为正整数，而所有的 $b_i$ 初始值均为 $0$。在游戏的每一轮中，Faraz 可以选择一个下标 $i$ ($1 \le i \le n$)，并将 $b_i$ 增加或减少 $a_i$。也就是说，他可以将 $b_i$ 更新为 $b_i + a_i$ 或 $b_i - a_i$。

游戏的目标是在经过若干轮操作后，使得序列 $b$ 严格递增，即满足 $b_1 < b_2 < \dots < b_n$。

Faraz 很懒，他想用最少的轮数达到游戏目标。他甚至懒得自己去计算，于是他问你：最少需要多少轮操作？

输入格式

第一行包含一个整数 $n$，表示序列 $a$ 和 $b$ 的长度。

第二行包含 $n$ 个整数，依次表示序列 $a_1, a_2, \dots, a_n$。

输出格式

在唯一的一行中输出 Faraz 所需的最少操作轮数。

数据范围

$1 \le n \le 5000$ $1 \le a_i \le 10^9$

样例

样例输入 1

5
1 2 3 4 5

样例输出 1

4

样例输入 2

7
1 2 1 2 1 2 1

样例输出 2

10