Milena and Admirer
Contest: Codeforces Round 910 (Div. 2)
Difficulty rating: 1500
Tags: greedy, math

Milena has received an array of integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$ from a secret admirer. She thinks that making it non-decreasing should help her identify the secret admirer.

She can use the following operation to make this array non-decreasing:

- Select an element $$$a_i$$$ of array $$$a$$$ and an integer $$$x$$$ such that $$$1 \le x < a_i$$$. Then, replace $$$a_i$$$ by two elements $$$x$$$ and $$$a_i - x$$$ in array $$$a$$$. New elements ($$$x$$$ and $$$a_i - x$$$) are placed in the array $$$a$$$ in this order instead of $$$a_i$$$.More formally, let $$$a_1, a_2, \ldots, a_i, \ldots, a_k$$$ be an array $$$a$$$ before the operation. After the operation, it becomes equal to $$$a_1, a_2, \ldots, a_{i-1}, x, a_i - x, a_{i+1}, \ldots, a_k$$$. Note that the length of $$$a$$$ increases by $$$1$$$ on each operation.

Milena can perform this operation multiple times (possibly zero). She wants you to determine the minimum number of times she should perform this operation to make array $$$a$$$ non-decreasing.

An array $$$x_1, x_2, \ldots, x_k$$$ of length $$$k$$$ is called non-decreasing if $$$x_i \le x_{i+1}$$$ for all $$$1 \le i < k$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10\,000$$$). The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\leq a_i\leq 10^9$$$) – the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output one integer — the minimum number of operations required to make the array non-decreasing.

It can be shown that it is always possible to make the array $$$a$$$ non-decreasing in the finite number of operations.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Milena can replace the second element of array $$$a$$$ by integers $$$1$$$ and $$$2$$$, so the array would become $$$[\, 1, \, \underline{1}, \, \underline{2}, \, 2 \,]$$$. Only $$$1$$$ operation is required.

In the second test case, the array $$$a$$$ is already non-decreasing, so the answer is $$$0$$$.

In the third test case, Milena can make array $$$a$$$ non-decreasing in $$$3$$$ operations as follows.

- Select $$$i=1$$$ and $$$x=2$$$ and replace $$$a_1$$$ by $$$2$$$ and $$$1$$$. The array $$$a$$$ becomes equal to $$$[\, \underline{2}, \, \underline{1}, \, 2, \, 1 \, ]$$$.
- Select $$$i=3$$$ and $$$x=1$$$ and replace $$$a_3$$$ by $$$1$$$ and $$$1$$$. The array $$$a$$$ becomes equal to $$$[\, 2, \, 1, \, \underline{1}, \, \underline{1}, \, 1 \,]$$$.
- Select $$$i=1$$$ and $$$x=1$$$ and replace $$$a_1$$$ by $$$2$$$ and $$$1$$$. The array $$$a$$$ becomes equal to $$$[\, \underline{1}, \, \underline{1}, \, 1, \, 1, \, 1, \, 1 \,]$$$.

It can be shown that it is impossible to make it non-decreasing in $$$2$$$ or less operations, so the answer is $$$3$$$.

Example input:
4
3
1 3 2
4
1 2 3 4
3
3 2 1
7
1 4 4 3 5 7 6

Example output:
1
0
3
9

Editorial:
Try a greedy approach. That is, split each $$$a_i$$$ only as many times as necessary (and try to create almost equal parts).
We will iterate over the array from right to left. Then, as described in the hint section, we will split the current $$$a_i$$$ and create almost equal parts. For example, $$$5$$$ split into three parts forms the subarray $$$[1,2,2]$$$. Splitting $$$8$$$ into four parts forms the subarray $$$[2,2,2,2]$$$. Notice that the subarrays must be sorted. Because we want to perform as few splits as possible, the rightmost endpoint value should be as high as possible (as long as it is lower than or equal to the leftmost endpoint of the splitting of $$$a_{i+1}$$$ if it exists).
When we iterate over the array, it is enough to set the current $$$a_i$$$ to the leftmost endpoint of the splitting (the smallest current value). It will help to calculate the optimal splitting of $$$a_{i-1}$$$. For the current $$$a_i$$$, we want to find the least $$$k$$$ such that we can split $$$a_{i-1}$$$ into $$$k$$$ parts so the rightmost endpoint is less than or equal to $$$a_i$$$. More formally, we want $$$\lceil \frac{a_{i-1}}{k} \rceil \leq a_i$$$ to hold. Afterwards, we set $$$a_{i-1}$$$ to $$$\lfloor \frac{a_{i-1}}{k} \rfloor$$$ and continue with our algorithm. The simplest way to find the desired $$$k$$$ is to apply the following formula: $$$$$$k=\lceil \frac{a_{i-1}}{a_i} \rceil$$$$$$
The answer is the sum over all $$$k-1$$$.
There are $$$q \leq 2\cdot 10^5$$$ queries: given an index $$$i$$$ and an integer $$$x>1$$$, set $$$a_i := \lceil \frac{a_i}{x} \rceil$$$. Modify the array and print the answer to the original problem. Please note that the queries stack.