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