An optimist believes in the optimal usage of all options available.

Chef gives you $a sequence A_{1}, A_{2}, \ldots, A_{N}$ consisting of integers. You can perform the following operation on the sequence any number of times (possibly 0):
Select any continuous segment $A_{l \ldots r}$ and sort the segment in non-descending order, while keeping other elements unchanged. The cost to perform this operation is $max(A_{l \ldots r}) - min(A_{l \ldots r})$.

For example, if the sequence $A = [3, \textcolor{blue}{4,1,5,1} ,9]$ , then applying the operation on $A_{2 \ldots 5}$ yields the sequence $[3, \textcolor{blue}{1,1,4,5} ,9]$. The cost to perform this operation is 5-1 = 4 .

You have to determine the minimum total cost of operations so that the sequence A becomes sorted in non-descending order, which means for all 2 ≤ i ≤ N, the condition A_{i-1} ≤ A_{i} is satisfied.

------ Input Format ------

• The first line of the input contains a single integer T - the number of test cases. The test cases then follow.
• The first line of each test case contains a single integer N.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \ldots, A_{N}$.

------ Output Format ------

• For each test case, print the minimum total cost of operations so that the sequence A becomes sorted in non-descending order.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

------ subtasks ------

Subtask $1$ (20 points): $N ≤ 1000;$ $\Sigma{N} ≤ 2000$
Subtask $2$ (40 points): $A$ is a permutation from $1$ to $N$
Subtask $3$ (40 points): Original constraints

----- Sample Input 1 ------
3
4
1 3 6 7
3
10 1 4
6
3 1 3 3 4 3
----- Sample Output 1 ------
0
9
3
----- explanation 1 ------
- Test case $1$: The sequence is already sorted in non-descending order. So, we require $0$ operations and thus $0$ total cost.

• Test case $2$: We can apply the operation on $A_{1 \ldots 3}$ which converts $A$ into $[\textcolor{blue}{1,4,10}]$ which is sorted in non-descending order.
  So, the total cost is $10-1=9$. It can be shown that we can't sort $A$ with less than $9$ total cost.

• Test Case $3$: First, we can apply the operation on $A_{1 \ldots 4}$ which converts $A$ into $[\textcolor{blue}{1,3,3,3},4,3]$.
  Then, apply the operation on $A_{3 \ldots 6}$ which converts $A$ into $[1,3,\textcolor{blue}{3,3,3,4}]$ which is sorted in non-descending order.
  So, the total cost is $3-1 + 4-3 = 3$. It can be shown that we can't sort $A$ with less than $3$ total cost.

见题面

见题面