1987B.md (1863B)
1 Source: https://codeforces.com/problemset/problem/1987/B 2 3 B. K-Sort 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 You are given an array of integers $a$ of length $n$. 22 23 You can apply the following operation any number of times (maybe, zero): 24 25 * First, choose an integer $k$ such that $1 \le k \le n$ and pay $k + 1$ coins. 26 * Then, choose exactly $k$ indices such that $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$. 27 * Then, for each $x$ from $1$ to $k$, increase $a_{i_x}$ by $1$. 28 29 Find the minimum number of coins needed to make $a$ non-decreasing. That is, $a_1 \le a_2 \le \ldots \le a_n$. 30 31 Input 32 33 Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows. 34 35 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the array $a$. 36 37 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 40 41 Output 42 43 For each test case, output a single integer — the minimum number of coins needed to make $a$ non-decreasing. 44 45 Example 46 47 Input 48 49 ``` 50 5 51 52 3 53 54 1 7 9 55 56 5 57 58 2 1 4 7 6 59 60 4 61 62 1 3 2 4 63 64 1 65 66 179 67 68 9 69 70 344 12 37 60 311 613 365 328 675 71 ``` 72 73 Output 74 75 ``` 76 0 77 3 78 2 79 0 80 1821 81 ``` 82 83 Note 84 85 In the first test case, $a$ is already sorted, so you don't have to spend any coins. 86 87 In the second test case, the optimal sequence of operations is: 88 89 * Choose $k = 2$ and the indices $2$ and $5$: $[ 2, \color{red}{1}, 4, 7, \color{red}{6} ] \rightarrow [2, 2, 4, 7, 7]$. This costs $3$ coins. 90 91 It can be proven that it is not possible to make $a$ non-decreasing by spending less than $3$ coins.