Make it Increasing
Description
You are given an array $a$ consisting of $n$ positive integers, and an array $b$, with length $n$. Initially $b_i=0$ for each $1 \leq i \leq n$.
In one move you can choose an integer $i$ ($1 \leq i \leq n$), and add $a_i$ to $b_i$ or subtract $a_i$ from $b_i$. What is the minimum number of moves needed to make $b$ increasing (that is, every element is strictly greater than every element before it)?
The first line contains a single integer $n$ ($2 \leq n \leq 5000$).
The second line contains $n$ integers, $a_1$, $a_2$, ..., $a_n$ ($1 \leq a_i \leq 10^9$) — the elements of the array $a$.
Print a single integer, the minimum number of moves to make $b$ increasing.
Input
The first line contains a single integer $n$ ($2 \leq n \leq 5000$).
The second line contains $n$ integers, $a_1$, $a_2$, ..., $a_n$ ($1 \leq a_i \leq 10^9$) — the elements of the array $a$.
Output
Print a single integer, the minimum number of moves to make $b$ increasing.
Samples
5
1 2 3 4 5
4
7
1 2 1 2 1 2 1
10
8
1 8 2 7 3 6 4 5
16
Note
Example $1$: you can subtract $a_1$ from $b_1$, and add $a_3$, $a_4$, and $a_5$ to $b_3$, $b_4$, and $b_5$ respectively. The final array will be [$-1$, $0$, $3$, $4$, $5$] after $4$ moves.
Example $2$: you can reach [$-3$, $-2$, $-1$, $0$, $1$, $2$, $3$] in $10$ moves.