K-Sort
Contest: EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)
Difficulty rating: 1000
Tags: greedy

You are given an array of integers $$$a$$$ of length $$$n$$$.

You can apply the following operation any number of times (maybe, zero):

- First, choose an integer $$$k$$$ such that $$$1 \le k \le n$$$ and pay $$$k + 1$$$ coins.
- Then, choose exactly $$$k$$$ indices such that $$$1 \le i_1 < i_2 < \ldots < i_k \le n$$$.
- Then, for each $$$x$$$ from $$$1$$$ to $$$k$$$, increase $$$a_{i_x}$$$ by $$$1$$$.

Find the minimum number of coins needed to make $$$a$$$ non-decreasing. That is, $$$a_1 \le a_2 \le \ldots \le a_n$$$.

Input format:
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.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 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 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

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

Output format:
For each test case, output a single integer — the minimum number of coins needed to make $$$a$$$ non-decreasing.

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

Note:
In the first test case, $$$a$$$ is already sorted, so you don't have to spend any coins.

In the second test case, the optimal sequence of operations is:

- 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.

Example input:
5
3
1 7 9
5
2 1 4 7 6
4
1 3 2 4
1
179
9
344 12 37 60 311 613 365 328 675

Example output:
0
3
2
0
1821

Editorial:
Suppose that after all of the operations, the value at index $$$i$$$ has been increased by $$$b_i$$$. Notice that our cost can be factored into two parts: $$$k$$$ is responsible for how many elements we choose, and $$$1$$$ is responsible for how many operations we apply.
Since we have to apply at least $$$\max(b_i)$$$ operations, and over all operations we select a total of $$$\sum{b_i}$$$ elements, we have to pay at least $$$\sum{b_i} + \max(b_i)$$$ coins. This bound is also achievable, if on the $$$m$$$-th operation (numbered from $$$1$$$ to $$$\max(b_i)$$$) we select all indices with $$$b_i \ge m$$$.
Suppose the resulting array is sorted ($$$a_1 + b_1 \le a_2 + b_2 \le \ldots \le a_n + b_n$$$). Then, $$$a_i + b_i \le a_j + b_j$$$ must hold for all $$$1 \le i \le j \le n$$$. Using $$$b_i \ge 0$$$, we get $$$a_j + b_j \ge a_i + b_i \ge a_i \implies b_j \ge a_i - a_j$$$ for all $$$1 \le i \le j$$$. If we define $$$p_j := max(a_1, \ldots, a_j)$$$, we get $$$b_j \ge p_j - a_j$$$. This gives the lower bounds $$$\sum{b_i} \ge \sum(p_i - a_i)$$$ and $$$\max(b_i) \ge \max(p_i - a_i)$$$. Setting $$$b_i := p_i - a_i$$$ achieves them, so the answer to our problem is $$$\sum(p_i - a_i) + \max(p_i - a_i)$$$ coins.
Complexity: $$$\mathcal{O}(n)$$$
Note: it's possible to simulate the process on the values of $$$b$$$ (described above) in $$$\mathcal{O}(n \log n)$$$.