310842: CF1898B. Milena and Admirer
Description
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$.
InputEach 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$.
OutputFor 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.
ExampleInput4 3 1 3 2 4 1 2 3 4 3 3 2 1 7 1 4 4 3 5 7 6Output
1 0 3 9Note
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$.
Output
Milena 收到了一个由整数组成的数组 $a_1, a_2, \ldots, a_n$,长度为 $n$,作为她的秘密仰慕者送来的礼物。她认为将这个数组变为非递减数组能帮助她识别出这个秘密仰慕者。
她可以使用以下操作使数组变为非递减:
1. 选择数组 $a$ 的一个元素 $a_i$ 和一个整数 $x$,使得 $1 \le x < a_i$。然后将 $a_i$ 替换为两个元素 $x$ 和 $a_i - x$。新元素($x$ 和 $a_i - x$)按此顺序放入数组 $a$ 中,替换 $a_i$。更正式地说,假设操作前数组 $a$ 为 $a_1, a_2, \ldots, a_i, \ldots, a_k$,则操作后数组变为 $a_1, a_2, \ldots, a_{i-1}, x, a_i - x, a_{i+1}, \ldots, a_k$。注意,每次操作后数组 $a$ 的长度增加 $1$。
Milena 可以执行此操作多次(可能为零次)。她想要你确定她至少需要执行多少次此操作才能使数组 $a$ 变为非递减。
一个长度为 $k$ 的数组 $x_1, x_2, \ldots, x_k$ 如果对于所有 $1 \le i < k$ 满足 $x_i \le x_{i+1}$,则称为非递减数组。
**输入数据格式**:
每个测试包含多个测试案例。第一行包含测试案例的数量 $t$($1 \leq t \leq 10\,000$)。接下来是每个测试案例的描述。
每个测试案例的第一行包含一个整数 $n$($1 \leq n \leq 2 \cdot 10^5$)——数组 $a$ 的长度。
每个测试案例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$($1 \leq a_i \leq 10^9$)——数组 $a$。
保证所有测试案例的 $n$ 之和不超过 $2 \cdot 10^5$。
**输出数据格式**:
对于每个测试案例,输出一个整数——使数组变为非递减所需的最小操作次数。
可以证明,在有限次操作后总是可以使数组 $a$ 变为非递减。**题目大意**: Milena 收到了一个由整数组成的数组 $a_1, a_2, \ldots, a_n$,长度为 $n$,作为她的秘密仰慕者送来的礼物。她认为将这个数组变为非递减数组能帮助她识别出这个秘密仰慕者。 她可以使用以下操作使数组变为非递减: 1. 选择数组 $a$ 的一个元素 $a_i$ 和一个整数 $x$,使得 $1 \le x < a_i$。然后将 $a_i$ 替换为两个元素 $x$ 和 $a_i - x$。新元素($x$ 和 $a_i - x$)按此顺序放入数组 $a$ 中,替换 $a_i$。更正式地说,假设操作前数组 $a$ 为 $a_1, a_2, \ldots, a_i, \ldots, a_k$,则操作后数组变为 $a_1, a_2, \ldots, a_{i-1}, x, a_i - x, a_{i+1}, \ldots, a_k$。注意,每次操作后数组 $a$ 的长度增加 $1$。 Milena 可以执行此操作多次(可能为零次)。她想要你确定她至少需要执行多少次此操作才能使数组 $a$ 变为非递减。 一个长度为 $k$ 的数组 $x_1, x_2, \ldots, x_k$ 如果对于所有 $1 \le i < k$ 满足 $x_i \le x_{i+1}$,则称为非递减数组。 **输入数据格式**: 每个测试包含多个测试案例。第一行包含测试案例的数量 $t$($1 \leq t \leq 10\,000$)。接下来是每个测试案例的描述。 每个测试案例的第一行包含一个整数 $n$($1 \leq n \leq 2 \cdot 10^5$)——数组 $a$ 的长度。 每个测试案例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$($1 \leq a_i \leq 10^9$)——数组 $a$。 保证所有测试案例的 $n$ 之和不超过 $2 \cdot 10^5$。 **输出数据格式**: 对于每个测试案例,输出一个整数——使数组变为非递减所需的最小操作次数。 可以证明,在有限次操作后总是可以使数组 $a$ 变为非递减。