Faraz has participated in a game, but he is not very interested in it. The game is described as follows: Faraz is faced with two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$, where all $a_i$ are positive and all $b_i$ are initially zero. In each step of the game, Faraz chooses an arbitrary index $i$ ($1 \le i \le n$) and adds or subtracts $a_i$ from $b_i$. That is, he sets $b_i \leftarrow b_i + a_i$ or $b_i \leftarrow b_i - a_i$.

The goal of the game is to make the sequence $b$ strictly increasing after a number of steps. That is, we must have $b_1 < b_2 < \dots < b_n$.

Faraz, who is not interested, wants to reach the goal in the minimum number of steps. Since he does not even have the patience to do this himself, he has asked you what this minimum number of steps is.

Input

The first line contains the integer $n$, which represents the length of the two sequences $a$ and $b$.

The second line contains $n$ integers, which represent the sequence $a_1, a_2, \dots, a_n$ in order.

Output

Print the minimum number of steps required for Faraz's game on a single line.

Constraints

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

Examples

Input 1

5
1 2 3 4 5

Output 1

4

Input 2

7
1 2 1 2 1 2 1

Output 2

10