[Solution] Make it Increasing solution codeforces

Make it Increasing solution codeforces – You are given an array 𝑎a consisting of 𝑛n positive integers, and an array 𝑏b, with length 𝑛n. Initially 𝑏𝑖=0bi=0 for each 1𝑖𝑛1≤i≤n.

[Solution] Make it Increasing solution codeforces

In one move you can choose an integer 𝑖i (1𝑖𝑛1≤i≤n), and add 𝑎𝑖ai to 𝑏𝑖bi or subtract 𝑎𝑖ai from 𝑏𝑖bi. What is the minimum number of moves needed to make 𝑏b increasing (that is, every element is strictly greater than every element before it)?

Input

The first line contains a single integer 𝑛n (2𝑛50002≤n≤5000).

The second line contains 𝑛n integers, 𝑎1a1𝑎2a2, …, 𝑎𝑛an (1𝑎𝑖1091≤ai≤109) — the elements of the array 𝑎a.

Output

Print a single integer, the minimum number of moves to make 𝑏b increasing.

[Solution] Make it Increasing solution codeforces

Examples
input

Copy
5
1 2 3 4 5
output

Copy
4
input

Copy
7
1 2 1 2 1 2 1
output

Copy
10
input

Copy
8
1 8 2 7 3 6 4 5

Make it Increasing solution codeforces

output

Copy
16
Note

Example 11: you can subtract 𝑎1a1 from 𝑏1b1, and add 𝑎3a3𝑎4a4, and 𝑎5a5 to 𝑏3b3𝑏4b4, and 𝑏5b5 respectively. The final array will be [1−100334455] after 44 moves.

Example 22: you can reach [3−32−21−100112233] in 1010 moves.

 

For Solution

Click here

Leave a Comment