You are given an array of integers $$$a$$$ of length $$$n$$$.
You can apply the following operation any number of times (maybe, zero):
Find the minimum number of coins needed to make $$$a$$$ non-decreasing. That is, $$$a_1 \le a_2 \le \ldots \le a_n$$$.
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$$$.
For each test case, output a single integer — the minimum number of coins needed to make $$$a$$$ non-decreasing.
531 7 952 1 4 7 641 3 2 411799344 12 37 60 311 613 365 328 675
0 3 2 0 1821
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:
Name |
---|