1898B.md (3109B)
1 Source: https://codeforces.com/problemset/problem/1898/B 2 3 B. Milena and Admirer 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 She can use the following operation to make this array non-decreasing: 24 25 * Select an element $a_i$ of array $a$ and an integer $x$ such that $1 \le x \lt 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$. 26 27 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. 28 29 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. 30 31 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 \lt k$. 32 33 Input 34 35 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. 36 37 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$. 38 39 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$. 40 41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 42 43 Output 44 45 For each test case, output one integer — the minimum number of operations required to make the array non-decreasing. 46 47 It can be shown that it is always possible to make the array $a$ non-decreasing in the finite number of operations. 48 49 Example 50 51 Input 52 53 ``` 54 4 55 56 3 57 58 1 3 2 59 60 4 61 62 1 2 3 4 63 64 3 65 66 3 2 1 67 68 7 69 70 1 4 4 3 5 7 6 71 ``` 72 73 Output 74 75 ``` 76 1 77 0 78 3 79 9 80 ``` 81 82 Note 83 84 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. 85 86 In the second test case, the array $a$ is already non-decreasing, so the answer is $0$. 87 88 In the third test case, Milena can make array $a$ non-decreasing in $3$ operations as follows. 89 90 * 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 \, ]$. 91 * 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 \,]$. 92 * 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 \,]$. 93 94 It can be shown that it is impossible to make it non-decreasing in $2$ or less operations, so the answer is $3$.