New update is available. Click here to update.

Topics

Ninja is a brilliant student in the class, so his teacher assigned him a problem.

He has been given an array ‘A’ containing positive integers ‘N’ integers.

He has also been given another array ‘B’ of size ‘N’ initially filled with 0’s at all the positions.

Now, In one move, Ninja can update any ‘B[i]’ as ‘B[i] - A[i]’ or as ‘B[i] + A[i]’, and he has been asked to find the minimum number of moves to make this array ‘B’ strictly increasing.

Your task is to help Ninja and print the minimum number of the above moves to make the array ‘B’ strictly increase.

```
Input: ‘N’ = 5, ‘A’ = [1, 2, 3, 4, 5]
Output: 4
Initially, array ‘B = [0, 0, 0, 0, 0], we will perform the following sequence of moves:
‘B[0] = B[0] - A[0]’
‘B[2] = B[2] + A[2]’
‘B[3] = B[3] + A[3]’
‘B[4] = B[4] + A[4]’
After these moves, the updated array will be [-1, 0, 3, 4, 5], and this is the minimum possible number of moves to make this array strictly increase.
```

Detailed explanation

```
1 ≤ T ≤ 10
2 ≤ N ≤ 10^3
1 ≤ A[i] ≤ 10^9
It is guaranteed that the sum of 'N' is ≤ 10^3 over all test cases.
Time limit: 1 sec
```

```
2
2
2 2
7
1 2 1 2 1 2 1
```

```
1
10
```

```
For test case 1:
Initially, the array ‘B’ = [0, 0] by one move, we can make it [0, 2], and hence the answer is 1.
For test case 2:
Initially, the array ‘B’ = [0, 0, 0, 0, 0, 0, 0] by 10 moves we can make it [−3, −2, −1, 0, 1, 2, 3], and hence the answer is 10. Here 10 is the minimum possible number of moves needed to make this array strictly increasing.
```

```
2
4
2 4 1 1
6
2 1 4 1 3 5
```

```
4
5
```