CF1898B.Milena and Admirer
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Milena has received an array of integers a1,a2,…,an 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 ai of array a and an integer x such that 1≤x<ai . Then, replace ai by two elements x and ai−x in array a . New elements ( x and ai−x ) are placed in the array a in this order instead of ai .More formally, let a1,a2,…,ai,…,ak be an array a before the operation. After the operation, it becomes equal to a1,a2,…,ai−1,x,ai−x,ai+1,…,ak . 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 x1,x2,…,xk of length k is called non-decreasing if xi≤xi+1 for all 1≤i<k .
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤10000 ). The description of test cases follows.
The first line of each test case contains a single integer n ( 1≤n≤2⋅105 ) — the length of the array a .
The second line of each test case contains n integers a1,a2,…,an ( 1≤ai≤109 ) – the array a .
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 .
输出格式
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.
输入输出样例
输入#1
4 3 1 3 2 4 1 2 3 4 3 3 2 1 7 1 4 4 3 5 7 6
输出#1
1 0 3 9
说明/提示
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,1,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 a1 by 2 and 1 . The array a becomes equal to [2,1,2,1] .
- Select i=3 and x=1 and replace a3 by 1 and 1 . The array a becomes equal to [2,1,1,1,1] .
- Select i=1 and x=1 and replace a1 by 2 and 1 . The array a becomes equal to [1,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 .