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

Difficulty: HARD
Tags: Sorting

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	hm1 = dict()
	hm2 = dict()
	ans = 0
	M = float('-inf')
	m = float('inf')
	sort_ar = sorted(ar)
	for i in range(n):
		m = min(m, ar[i])
		M = max(M, ar[i])
		if ar[i] not in hm2:
			if ar[i] not in hm1:
				hm1[ar[i]] = 1
			else:
				hm1[ar[i]] += 1
		elif hm2[ar[i]] > 1:
			hm2[ar[i]] -= 1
		else:
			del hm2[ar[i]]
		if sort_ar[i] not in hm1:
			if sort_ar[i] not in hm2:
				hm2[sort_ar[i]] = 1
			else:
				hm2[sort_ar[i]] += 1
		elif hm1[sort_ar[i]] > 1:
			hm1[sort_ar[i]] -= 1
		else:
			del hm1[sort_ar[i]]
		if len(hm1) == 0 and len(hm2) == 0:
			ans += M - m
			M = float('-inf')
			m = float('inf')
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	li = sorted(l)
	x = 0
	ans = 0
	while x < n:
		mx = li[x]
		mn = li[x]
		for j in range(x, n + 1):
			mx = max(mx, l[j])
			if mx == li[j]:
				ans += mx - mn
				x = j + 1
				break
	print(ans)


ans = ''
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = arr.copy()
	brr.sort()
	res = 0
	maxNum = arr[0]
	minNum = brr[0]
	(sumA, sumB) = (0, 0)
	for i in range(n):
		sumA += arr[i]
		sumB += brr[i]
		maxNum = max(maxNum, arr[i])
		if sumA == sumB:
			res += maxNum - minNum
			if i + 1 < n:
				maxNum = arr[i + 1]
				minNum = brr[i + 1]
			(sumA, sumB) = (0, 0)
	ans += str(res) + '\n'
print(ans)


for sharma in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	i = 0
	ans1 = 0
	while i < n:
		mn = b[i]
		mx = b[i]
		for j in range(i, n + 1):
			mx = max(mx, a[j])
			if mx == b[j]:
				ans1 += mx - mn
				i = j + 1
				break
	print(ans1)


for t in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	sortedA = list(A)
	sortedA.sort()
	i = 0
	cost = 0
	while i < len(A):
		j = int(i)
		while j < len(A):
			temp = A[i:j + 1]
			temp.sort()
			if temp == sortedA[i:j + 1]:
				cost += max(sortedA[i:j + 1]) - min(sortedA[i:j + 1])
				i = int(j + 1)
				break
			else:
				j += 1
	print(cost)


for _ in range(int(input())):
	n = int(input())
	no = list(map(int, input().split()))
	sno = sorted(no)
	ans = 0
	place = dict()
	for i in range(n):
		place[sno[i]] = i
	i = 0
	while i < n and no[i] == sno[i]:
		i += 1
	j = n - 1
	while j >= 0 and no[j] == sno[j]:
		j -= 1
	if j + 1 > i:
		ans = max(no[i:j + 1]) - min(no[i:j + 1])
		(intervals, count) = ([], 0)
		for k in range(i, j + 1):
			if no[k] != sno[k]:
				intervals.append([k, place[no[k]]])
				count += 1
		k = 0
		while k + 1 < count:
			if intervals[k][1] >= intervals[k + 1][0]:
				intervals[k][1] = max(intervals[k][1], intervals[k + 1][1])
				del intervals[k + 1]
				count -= 1
			else:
				k += 1
		t = 0
		for k in range(count):
			t += max(no[intervals[k][0]:intervals[k][1] + 1]) - min(no[intervals[k][0]:intervals[k][1] + 1])
		ans = min(ans, t)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	sa = sorted(a)
	place = dict()
	for i in range(n):
		place[sa[i]] = i
	i = 0
	while i < n and a[i] == sa[i]:
		i += 1
	j = n - 1
	while j >= 0 and a[j] == sa[j]:
		j -= 1
	if j + 1 > i:
		ans = max(a[i:j + 1]) - min(a[i:j + 1])
		(intervals, l) = ([], 0)
		for k in range(i, j + 1):
			if a[k] != sa[k]:
				intervals.append([k, place[a[k]]])
				l += 1
		k = 0
		while k + 1 < l:
			if intervals[k][1] >= intervals[k + 1][0]:
				intervals[k][1] = max(intervals[k][1], intervals[k + 1][1])
				del intervals[k + 1]
				l -= 1
			else:
				k += 1
		temp = 0
		for k in range(l):
			temp += max(a[intervals[k][0]:intervals[k][1] + 1]) - min(a[intervals[k][0]:intervals[k][1] + 1])
		ans = min(ans, temp)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = [(x, a[x]) for x in range(len(a))]
	a.sort(key=lambda i: i[1])
	output = 0
	s = -1
	e = -1
	for i in range(n):
		if s == -1:
			if a[i][0] != i:
				s = i
				e = a[i][0]
		elif a[i][0] > e:
			e = a[i][0]
		elif e == i:
			output += a[e][1] - a[s][1]
			e = -1
			s = -1
	print(output)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	s = 0
	mn = b[n - 1]
	mx = b[0]
	t = 0
	u = 0
	for j in range(n):
		if a[j] == b[j]:
			if t == 0:
				continue
			mn = min(mn, a[j])
			mx = max(mx, a[j])
		else:
			mn = min(mn, a[j])
			mx = max(mx, a[j])
			r = a[u:j + 1]
			r.sort()
			if r == b[u:j + 1]:
				s += mx - mn
				t = 0
				continue
			if t == 0:
				t = 1
				mn = a[j]
				mx = a[j]
				u = j
	if t == 1:
		t = 0
		s += mx - mn
	print(s)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mx = [0] * n
	mn = [0] * n
	mx[0] = a[0]
	mn[n - 1] = a[n - 1]
	for i in range(1, n):
		mx[i] = max(mx[i - 1], a[i])
	for i in range(n - 2, -1, -1):
		mn[i] = min(mn[i + 1], a[i])
	res = 0
	maxi = 0
	mini = 10 ** 12
	for i in range(n - 1):
		maxi = max(maxi, a[i])
		mini = min(mini, a[i])
		if mx[i] < mn[i + 1]:
			res += maxi - mini
			maxi = 0
			mini = 10 ** 12
	maxi = max(maxi, a[n - 1])
	mini = min(mini, a[n - 1])
	res += maxi - mini
	print(res)


import math
from collections import Counter

def calc(data):
	result = sorted(data)
	total = 0
	start = 0
	cnt = Counter()
	for i in range(len(data)):
		cnt[result[i]] += 1
		cnt[data[i]] -= 1
		if sum(cnt.elements()) == 0:
			if i > start:
				total += result[i] - result[start]
			start = i + 1
			cnt.clear()
	return total
for _ in range(int(input())):
	_ = input()
	data = list(map(int, input().split()))
	print(calc(data))


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	s_a = sorted(a)
	ab = []
	ba = []
	ans = 0
	last_ind = 0
	for i in range(n):
		ab.append(a[i])
		ba.append(s_a[i])
		if a[i] in ab and a[i] in ba:
			ab.remove(a[i])
			ba.remove(a[i])
		if s_a[i] in ab and s_a[i] in ba:
			ab.remove(s_a[i])
			ba.remove(s_a[i])
		if len(ab) == 0 and len(ba) == 0:
			ans = ans + s_a[i] - s_a[last_ind]
			last_ind = i + 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	count = 0
	i = 0
	dr = sorted(arr)
	j = n - 1
	while i < n:
		if arr[i] == dr[i]:
			i += 1
		else:
			break
	while j > 0:
		if arr[j] == dr[j]:
			j -= 1
		else:
			break
	d = {}
	for i in range(n):
		d[arr[i]] = i
	x = -1
	y = -1
	cost = 0
	f = i
	for i in range(n):
		if arr[i] == dr[i] and x == -1:
			continue
		if x == -1:
			y = i
		x = max(x, d[arr[i]])
		x = max(x, d[dr[i]])
		if x == i:
			cost += max(arr[y:i + 1]) - min(arr[y:i + 1])
			x = -1
	print(cost)


import bisect

def Cloning(arr):
	carr = []
	carr.extend(arr)
	return carr
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	arr2 = Cloning(arr)
	arr2.sort()
	ans = 0
	compare_arr = []
	compare_arr2 = []
	for i in range(n):
		bisect.insort(compare_arr, arr[i])
		compare_arr2.append(arr2[i])
		if compare_arr == compare_arr2:
			ans += abs(compare_arr[0] - compare_arr[len(compare_arr) - 1])
			compare_arr.clear()
			compare_arr2.clear()
	print(ans)
	t = t - 1


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	Answer = max(a) - min(a)
	ans = 0
	i = 0
	while i < n:
		if a[i] != b[i]:
			d1 = defaultdict(int)
			d2 = defaultdict(int)
			d1[a[i]] += 1
			d2[b[i]] += 1
			j = i + 1
			while j < n and d1 != d2:
				d1[a[j]] += 1
				d2[b[j]] += 1
				j += 1
			j -= 1
			ans += b[j] - b[i]
			i = j + 1
		else:
			i += 1
	print(min(ans, Answer))


def findans(l, n):
	sort_l = sorted(l)
	s = dict()
	t = dict()
	i = 0
	c = 0
	while i < n:
		if l[i] != sort_l[i]:
			s.clear()
			t.clear()
			s[l[i]] = 1
			t[sort_l[i]] = 1
			mini = sort_l[i]
			i += 1
			while i < n and t != s:
				maxi = sort_l[i]
				if s.get(l[i]):
					s[l[i]] += 1
				else:
					s[l[i]] = 1
				if t.get(sort_l[i]):
					t[sort_l[i]] += 1
				else:
					t[sort_l[i]] = 1
				i += 1
			c += maxi - mini
		else:
			i += 1
	return c
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(findans(l, n))


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	dp = [float('inf')] * n
	dp[-1] = A[-1]
	for i in range(n - 2, -1, -1):
		dp[i] = min(dp[i + 1], A[i])
	ans = 0
	i = 0
	mx = A[0]
	mn = float('inf')
	while i < n - 1:
		mx = max(mx, A[i])
		if mx <= dp[i]:
			i += 1
			mx = max(A[i], mx)
		else:
			mx = max(mx, A[i])
			mn = A[i]
			while mx > dp[i] and i < n - 1:
				mx = max(mx, A[i])
				i += 1
				mn = min(mn, A[i])
			ans += mx - mn
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = list(sorted(l))
	(m, m1) = ([], [])
	ans = 0
	for i in range(n):
		m.append(l[i])
		m1.append(l1[i])
		if sorted(m) == sorted(m1):
			ans += max(m1) - min(m1)
			m.clear()
			m1.clear()
		else:
			continue
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	aSort = sorted(a)
	cost = 0
	tmpA = list()
	tmpB = list()
	for i in range(n):
		tmpA.append(a[i])
		tmpB.append(aSort[i])
		tmpA.sort()
		tmpB.sort()
		if tmpA != tmpB:
			continue
		else:
			cost += max(tmpA) - min(tmpA)
			tmpA.clear()
			tmpB.clear()
	print(cost)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mx = [0] * n
	mn = [0] * n
	mx[0] = l[0]
	mn[n - 1] = l[n - 1]
	for i in range(1, n):
		mx[i] = max(l[i], mx[i - 1])
	for i in range(n - 2, -1, -1):
		mn[i] = min(l[i], mn[i + 1])
	ans = 0
	mxc = -10000000000000000
	mnc = 10000000000000000
	for i in range(n - 1):
		mxc = max(l[i], mxc)
		mnc = min(l[i], mnc)
		if mx[i] < mn[i + 1]:
			ans += mxc - mnc
			mxc = -10000000000000000
			mnc = 10000000000000000
	mxc = max(l[n - 1], mxc)
	mnc = min(l[n - 1], mnc)
	ans += mxc - mnc
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sorted(a)
	l1 = []
	l2 = []
	ans = 0
	for i in range(n):
		l1.append(a[i])
		l2.append(s[i])
		l1.sort()
		l2.sort()
		if l1 != l2:
			continue
		else:
			ans += max(l1) - min(l1)
			l1 = []
			l2 = []
	print(ans)


for _ in range(int(input())):
	l = int(input())
	arr = [int(i) for i in input().split()]
	arrs = sorted(arr)
	i = 0
	ans = 0
	while i < l:
		mx = arrs[i]
		mn = arrs[i]
		for j in range(i, l + 1):
			mx = max(mx, arr[j])
			if mx == arrs[j]:
				ans += mx - mn
				i = j + 1
				break
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	l = sorted(arr)
	if arr == l:
		print(0)
		continue
	i = 0
	ans = l[-1] - l[0]
	maxx = 0
	while i < n:
		if arr[i] != l[i]:
			dica = defaultdict(int)
			dicb = defaultdict(int)
			dica[arr[i]] += 1
			dicb[l[i]] += 1
			j = i + 1
			while j < n and dica != dicb:
				dica[arr[j]] += 1
				dicb[l[j]] += 1
				j += 1
			j -= 1
			maxx += l[j] - l[i]
			i = j + 1
		else:
			i += 1
	print(min(maxx, ans))


import math
import statistics

def func(N, arr):
	dp = [float('inf') for i in range(N)]
	dp[-1] = arr[-1]
	for i in range(N - 2, -1, -1):
		dp[i] = min(dp[i + 1], arr[i])
	ans = 0
	i = 0
	maxx = arr[0]
	minn = float('inf')
	while i < N - 1:
		maxx = max(maxx, arr[i])
		if maxx <= dp[i]:
			i += 1
			maxx = max(maxx, arr[i])
		else:
			maxx = max(maxx, arr[i])
			minn = arr[i]
			while maxx > dp[i] and i < N - 1:
				maxx = max(maxx, arr[i])
				i += 1
				minn = min(minn, arr[i])
			ans += maxx - minn
	return ans
T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	print(func(N, arr))


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	lsts = sorted(lst)
	ans = 0
	j = 0
	c1 = 0
	k = 0
	while j < n:
		if sorted(lst[k:j + 1]) == lsts[k:j + 1] and lsts[j] != lst[j]:
			ans += max(lsts[k:j + 1]) - min(lsts[k:j + 1])
			j += 1
			k = j
			c1 = 0
		elif lsts[j] == lst[j] and c1 == 0:
			j += 1
			k += 1
		else:
			j += 1
			c1 += 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l2 = sorted(l)
	l3 = []
	c = l[0]
	ans = 0
	for j in l:
		if j > c:
			c = j
		l3.append(c)
	k = 0
	for j in range(n):
		if l2[j] == l3[j]:
			ans = ans + l3[j] - min(l2[k:j + 1])
			k = j + 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [i for i in a]
	b.sort()
	i = 0
	ans = 0
	while i < n:
		while i < n and a[i] == b[i]:
			i += 1
		if i >= n:
			break
		mx = a[i]
		mn = b[i]
		c = 0
		while i < n:
			if mx == a[i]:
				c += 1
			elif mx < a[i]:
				mx = a[i]
				c = 1
			if mx == b[i]:
				c -= 1
			i += 1
			if c == 0:
				ans += mx - mn
				break
	print(ans)


import math
n = int(input())
for _ in range(n):
	s = int(input())
	A = list(map(int, input().split()))
	dp = [math.inf] * s
	dp[-1] = A[-1]
	for i in range(s - 2, -1, -1):
		dp[i] = min(dp[i + 1], A[i])
	Ans = 0
	i = 0
	mx = A[0]
	mn = math.inf
	while i < s - 1:
		mx = max(mx, A[i])
		if mx <= dp[i]:
			i += 1
			mx = max(mx, A[i])
		else:
			mx = max(mx, A[i])
			mn = A[i]
			while mx > dp[i] and i < s - 1:
				mx = max(mx, A[i])
				i += 1
				mn = min(mn, A[i])
			Ans += mx - mn
	print(Ans)


from typing import Counter

def binary_search(arr, low, high, x):
	if high >= low:
		mid = (high + low) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return binary_search(arr, low, mid - 1, x)
		else:
			return binary_search(arr, mid + 1, high, x)
	else:
		return -1

def f(l, x):
	return l.index(x)

def last(l, n, x):
	return n - 1 - l[::-1].index(x)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	sl = sorted(l)
	ans = 0
	d1 = Counter()
	d2 = Counter()
	lis = []
	i = 0
	start = 0
	while i < n:
		d1[l[i]] += 1
		d2[sl[i]] += 1
		if d1 == d2:
			lis.append((start, i))
			start = i + 1
			d1 = Counter()
			d2 = Counter()
		i += 1
	for i in lis:
		ans += sl[i[1]] - sl[i[0]]
	print(ans)


import math
import collections
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect_left as bsl
from bisect import bisect_right as bsr
import heapq as hq
setrecursionlimit(2 ** 20)
t = 1
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().rstrip().split()))
	b = []
	for i in range(n):
		b.append((a[i], i))
	b.sort()
	seg = []
	for i in range(n):
		seg.append([min(i, b[i][1]), max(i, b[i][1])])
	seg.sort()
	m_seg = []
	prv = seg[0][:]
	for i in range(1, len(seg)):
		if prv[1] >= seg[i][0]:
			prv[1] = max(seg[i][1], prv[1])
		else:
			m_seg.append(prv)
			prv = seg[i][:]
	m_seg.append(prv)
	ans = 0
	for j in m_seg:
		mi = 10 ** 9 + 1
		mx = -1
		for i in range(j[0], j[1] + 1):
			mi = min(a[i], mi)
			mx = max(a[i], mx)
		ans += mx - mi
	print(min(ans, max(a) - min(a)))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a1 = [0] * n
	a2 = [0] * n
	big = a[0]
	for i in range(n):
		if big < a[i]:
			big = a[i]
		a1[i] = big
	small = a[-1]
	for i in range(n - 1, -1, -1):
		if small > a[i]:
			small = a[i]
		a2[i] = small
	ans = 0
	r = 10 ** 18
	for i in range(n - 1, -1, -1):
		if a[i] == a1[i]:
			if a[i] <= r:
				ans += a1[i] - a2[i]
			else:
				ans += r - a2[i]
			r = a2[i]
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = sorted(l)
	(a, b, ans) = (0, 0, 0)
	(mi, ma) = (1000000001, -1)
	for i in range(n):
		a += l[i]
		b += k[i]
		mi = min(mi, l[i])
		ma = max(ma, l[i])
		if a == b:
			ans += ma - mi
			(a, b) = (0, 0)
			(mi, ma) = (1000000001, -1)
	print(ans)


test = int(input())
for _ in range(test):
	number = int(input())
	array = list(map(int, input().split()))
	sort = sorted(array)
	temp = 0
	Answer = 0
	while temp < number:
		new1 = sort[temp]
		new2 = sort[temp]
		for n in range(temp, number + 1):
			new2 = max(new2, array[n])
			if new2 == sort[n]:
				Answer += new2 - new1
				temp = n + 1
				break
	print(Answer)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	sort_arr = sorted(arr)
	dicti = {}
	for i in range(n - 1, -1, -1):
		if arr[i] in dicti:
			dicti[arr[i]].append(i)
		else:
			dicti[arr[i]] = [i]
	start = 0
	end = 0
	ans = 0
	for i in range(n):
		ind = dicti[sort_arr[i]].pop()
		end = max(end, ind)
		if i == end:
			ans += sort_arr[end] - sort_arr[start]
			start = end + 1
	print(ans)


import sys
try:
	for t in range(int(sys.stdin.readline())):
		n = int(sys.stdin.readline())
		a = list(map(int, sys.stdin.readline().split()))
		d = sorted(a)
		i = 0
		j = n - 1
		st = -1
		ed = -1
		while i < j:
			if d[i] == a[i] and st == -1:
				i = i + 1
			elif st == -1:
				st = i
			if d[j] == a[j] and ed == -1:
				j = j - 1
			elif ed == -1:
				ed = j
			if st != -1 and ed != -1:
				break
		if st == -1 and ed == -1:
			print(0)
			continue
		d1 = {}
		d2 = {}
		ma = d[ed] - d[st]
		temp = 0
		j = st
		for i in range(st, ed + 1):
			if a[i] == d[i] and d1 == d2:
				d1 = {}
				d2 = {}
				j = i + 1
			else:
				if a[i] not in d1.keys():
					d1[a[i]] = 1
				else:
					d1[a[i]] = d1[a[i]] + 1
				if d[i] not in d2.keys():
					d2[d[i]] = 1
				else:
					d2[d[i]] = d2[d[i]] + 1
				if d1 == d2:
					temp = temp + d[i] - d[j]
					d1 = {}
					d2 = {}
					j = i + 1
		print(temp)
except EOFError as e:
	pass


import sys
from collections import defaultdict
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = a[:]
	b.sort()
	ind = defaultdict(lambda : -1)
	for i in range(n):
		ind[a[i]] = i
	x = -1
	y = -1
	for i in range(n):
		if a[i] != b[i]:
			y = i
			break
	cost = 0
	for i in range(n):
		if a[i] == b[i] and x == -1:
			continue
		if x == -1:
			y = i
		x = max(x, ind[b[i]])
		x = max(x, ind[a[i]])
		if i == x:
			a[y:x + 1] = sorted(a[y:x + 1])
			cost += a[x] - a[y]
			x = -1
	print(cost)


from sys import *
from bisect import *
input = stdin.readline
for u in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = sorted(l)
	x = n - 1
	s = 0
	while x > 0:
		if l[x] != d[x]:
			(mx, mn) = (d[x], l[x])
			i = x
			while i > 0:
				if l[i] != d[x]:
					i -= 1
				else:
					break
				mn = min(mn, l[i])
			p = bisect_left(d, mn)
			for j in range(p, i):
				mn = min(mn, l[j])
			while d[p] != mn:
				p = bisect_left(d, mn)
				for j in range(p, i):
					mn = min(mn, l[j])
			s += mx - mn
			x = p - 1
		else:
			x -= 1
	print(s)


import bisect
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	st = n - 1
	ans = 0
	while st > 0:
		if a[st] != b[st]:
			ma = b[st]
			mi = a[st]
			i = st
			while i > 0:
				if a[i] != b[st]:
					i -= 1
				else:
					break
				mi = min(a[i], mi)
			pos = bisect.bisect_left(b, mi)
			for j in range(pos, i):
				mi = min(mi, a[j])
			while b[pos] != mi:
				pos = bisect.bisect_left(b, mi)
				for j in range(pos, i):
					mi = min(mi, a[j])
			ans += ma - mi
			st = pos - 1
		else:
			st -= 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	nos = list(map(int, input().split()))
	exp = sorted(nos)
	i = 0
	ans = 0
	while i < n:
		expd = {exp[i]: 1}
		avd = {nos[i]: 1}
		j = i + 1
		(mini, maxi) = (nos[i], nos[i])
		while j < n and expd != avd:
			if nos[j] < mini:
				mini = nos[j]
			elif nos[j] > maxi:
				maxi = nos[j]
			if nos[j] in avd:
				avd[nos[j]] += 1
			else:
				avd[nos[j]] = 1
			if exp[j] in expd:
				expd[exp[j]] += 1
			else:
				expd[exp[j]] = 1
			j += 1
		ans += maxi - mini
		i = j
	print(ans)


import bisect
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = sorted(arr[:])
	j = n - 1
	i = 0
	ans = 0
	while j > 0:
		if arr[j] != arr1[j]:
			x = arr1[j]
			y = arr[j]
			i = j
			while i:
				if arr[i] != arr1[j]:
					i -= 1
				else:
					break
				y = min(arr[i], y)
			low = bisect.bisect_left(arr1, y)
			for k in range(low, i):
				y = min(y, arr[k])
			while arr1[low] != y:
				low = bisect.bisect_left(arr1, y)
				for k in range(low, i):
					y = min(y, arr[k])
			ans += x - y
			j = low - 1
		else:
			j -= 1
	print(ans)


from sys import stdin
input = stdin.readline

def answer():
	(ans, i, j, d) = (0, 0, 0, dict())
	while i < n:
		d.clear()
		while i < n:
			d[a[i]] = d.get(a[i], 0) + 1
			while j < n and d.get(b[j], 0):
				d[b[j]] -= 1
				j += 1
			if i + 1 == j:
				ans += max(d.keys()) - min(d.keys())
				break
			i += 1
		i += 1
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	print(answer())


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import defaultdict as dd
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdmap = lambda : map(int, stdstr().split())
stdarr = lambda : list(map(int, stdstr().split()))
mod = 1000000007

class RangeQuery:

	def __init__(self, data, func=min):
		self.func = func
		self._data = _data = [list(data)]
		(i, n) = (1, len(_data[0]))
		while 2 * i <= n:
			prev = _data[-1]
			_data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
			i <<= 1

	def query(self, start, stop):
		depth = (stop - start).bit_length() - 1
		return self.func(self._data[depth][start], self._data[depth][stop - (1 << depth)])
for _ in range(stdint()):
	n = stdint()
	arr = stdarr()
	pairs = []
	for i in range(n):
		pairs.append((arr[i], i))
	pairs.sort()
	ranges = set()
	for i in range(n):
		if pairs[i][1] != i:
			ranges.add((min(i, pairs[i][1]), max(i, pairs[i][1])))
	if len(ranges) == 0:
		print(0)
	else:
		ranges = sorted(list(ranges))
		ma = RangeQuery(arr, func=max)
		mi = RangeQuery(arr, func=min)

		def getF(i, j):
			return ma.query(i, j + 1) - mi.query(i, j + 1)
		merged = [ranges[0]]
		for i in range(1, len(ranges)):
			curr = ranges[i]
			prev = merged[-1]
			if curr[0] <= prev[1]:
				l = min(prev[0], curr[0])
				r = max(prev[1], curr[1])
				merged[-1] = [l, r]
			else:
				merged.append(curr)
		res = 0
		for i in merged:
			res += getF(i[0], i[1])
		print(res)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	sorted_l = sorted(l)
	i = 0
	ans = 0
	while i < n:
		while i < n and l[i] == sorted_l[i]:
			i += 1
		if i < n:
			s1 = {l[i]: 1}
			s2 = {sorted_l[i]: 1}
			m = i
			i += 1
			while s1 != s2:
				s1[l[i]] = s1.get(l[i], 0) + 1
				s2[sorted_l[i]] = s2.get(sorted_l[i], 0) + 1
				i += 1
			ans += sorted_l[i - 1] - sorted_l[m]
	print(ans)


T = int(input())
for t in range(T):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arrs = [i for i in arr]
	arrs.sort()
	tot = 0
	mn = arrs[0]
	cost = 0
	encounter = dict()
	needed = dict()
	idx = 0
	for i in range(n):
		x = arr[i]
		if x == arrs[i]:
			tot += 1
		else:
			if arrs[i] in encounter and encounter[arrs[i]] > 0:
				encounter[arrs[i]] -= 1
				tot += 1
			elif arrs[i] in needed:
				needed[arrs[i]] += 1
			else:
				needed[arrs[i]] = 1
			if x in needed and needed[x] > 0:
				needed[x] -= 1
				tot += 1
			elif x in encounter:
				encounter[x] += 1
			else:
				encounter[x] = 1
		if tot == i - idx + 1:
			cost += arrs[i] - arrs[idx]
			if i != n - 1:
				mn = arrs[i + 1]
				idx = i + 1
			tot = 0
	print(cost)


import copy
import heapq
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	B = copy.deepcopy(A)
	B.sort()
	C = []
	heapq.heapify(C)
	i = 0
	start = 0
	ret = 0
	for x in A:
		if B[i] == x:
			i = i + 1
		else:
			heapq.heappush(C, x)
		while len(C) > 0 and C[0] == B[i]:
			heapq.heappop(C)
			i = i + 1
		if len(C) == 0:
			ret = ret + B[i - 1] - B[start]
			start = i
	print(ret)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a.copy()
	b.sort()
	ans = 0
	s = n - 1
	while s > 0:
		if a[s] != b[s]:
			p = b[s]
			q = a[s]
			i = s
			while i > 0:
				if a[i] != b[s]:
					i -= 1
				else:
					break
				q = min(q, a[i])
			pos = b.index(q)
			for j in range(pos, i):
				q = min(q, a[j])
			while b[pos] != q:
				pos = b.index(q)
				for j in range(pos, i):
					q = min(q, a[j])
			ans += p - q
			s = pos - 1
		else:
			s -= 1
	print(ans)


import sys
input = sys.stdin.readline
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	n = int(input())
	arr = [int(x) for x in input().split()]
	from_index = [y[0] for y in sorted(enumerate(arr), key=lambda x: (x[1], x[0]))]
	ans = 0
	start = 0
	smallest = float('inf')
	biggest = float('-inf')
	min_from_i = float('inf')
	max_from_i = float('-inf')
	num_elements_in_interval = 0
	for (i, from_i) in enumerate(from_index):
		x = arr[from_i]
		smallest = min(smallest, x)
		biggest = max(biggest, x)
		min_from_i = min(min_from_i, from_i)
		max_from_i = max(max_from_i, from_i)
		num_elements_in_interval += 1
		if min_from_i == start and max_from_i == i and (num_elements_in_interval == i - start + 1):
			ans += biggest - smallest
			start = i + 1
			smallest = float('inf')
			biggest = float('-inf')
			min_from_i = float('inf')
			max_from_i = float('-inf')
			num_elements_in_interval = 0
	print(ans)


for t in range(int(input())):
	n = int(input())
	A = [int(i) for i in input().split()]
	(A1, B) = (A[:], list())
	A1.sort()
	(d, d1) = (dict(), dict())
	for i in range(n):
		if A1[i] in d:
			d[A1[i]].append(i)
		else:
			d[A1[i]] = [i]
	for i in d:
		d1[i] = 0
	C1 = [int(i) for i in range(1, n + 1)]
	C2 = list()
	for i in range(n):
		x = d[A[i]][d1[A[i]]]
		C2.append(x + 1)
		d1[A[i]] += 1
	for i in range(1, n):
		C1[i] = C1[i - 1] + C1[i]
		C2[i] = C2[i - 1] + C2[i]
	(ref1, ref2) = (-1, -1)
	(ans, flag) = (0, 0)
	for i in range(n):
		if C1[i] == C2[i]:
			ref2 = i
			if flag:
				x = A1[ref2] - A1[ref1]
				ans += x
			else:
				pass
			flag = 0
		elif C1[i] != C2[i] and flag == 0:
			ref1 = i
			flag = 1
	print(ans)


from itertools import permutations as per
from math import factorial as fact
from difflib import SequenceMatcher
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [] + a
	b.sort()
	c = [-1] * n
	c[-1] = 10 ** 9 + 1
	for i in range(n - 2, -1, -1):
		c[i] = min(a[i + 1], c[i + 1])
	i = 0
	ans = 0
	while i < n:
		if a[i] == b[i]:
			i += 1
		else:
			j = i
			while c[i] <= b[i]:
				i += 1
			ans += b[i] - b[j]
			i += 1
	print(ans)


import sys
t = int(input())
while t:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	b = list()
	for i in range(n):
		b.append([a[i], i])
	b.sort()
	maxi = int(0)
	mini = int(1e+18)
	rr = 0
	res = 0
	for i in range(n):
		rr = max(rr, b[i][1])
		maxi = max(maxi, b[i][0])
		mini = min(mini, b[i][0])
		if rr == i:
			res += maxi - mini
			maxi = int(0)
			mini = int(1e+18)
		elif i == n - 1:
			res += maxi - mini
			maxi = int(0)
			mini = int(1e+18)
	print(res)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	sys.stderr = open('error.txt', 'w')
depth = 200001
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
linp = lambda : list(minp())
minp = lambda : map(int, input().split())
from math import inf, ceil, sqrt, log2, gcd
from collections import defaultdict, deque
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def expo(a, b):
	if not b:
		return 1
	v = expo(a, b // 2)
	v = v * v % mod
	if b % 2:
		v = v * a % mod
	return v

def modinv(a, b):
	d = expo(b, mod - 2)
	v = a * d % mod
	return v

def checkPrime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			return False
	return True

def highestPowerof2(x):
	x |= x >> 1
	x |= x >> 2
	x |= x >> 4
	x |= x >> 8
	x |= x >> 16
	return x ^ x >> 1

def isVowel(char):
	return char.lower() in 'aeiou'
for _ in range(int(input())):
	n = int(input())
	a = linp()
	b = sorted(a)
	d = defaultdict(lambda : [])
	for i in range(n):
		d[b[i]].append(i)
	for x in d.keys():
		d[x] = d[x][::-1]
	c = list()
	for i in range(n):
		c.append((a[i], d[a[i]][-1]))
		d[a[i]].pop()
	cost = 0
	(l, m) = (0, 0)
	for i in range(n):
		m = max(m, c[i][1])
		if m == i:
			(x, y) = (-1, inf)
			for j in range(l, m + 1):
				x = max(x, c[j][0])
				y = min(y, c[j][0])
			cost += x - y
			l = m + 1
			m = 0
	print(cost)


from sys import stdin
input = stdin.readline

def answer():
	(ans, i) = (0, 0)
	while i < n:
		(take1, take2) = ([], [])
		while i < n:
			take1.append(a[i])
			take2.append(b[i])
			if sorted(take1) == sorted(take2):
				ans += max(take1) - min(take1)
				break
			i += 1
		i += 1
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	print(answer())


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	ans = 0
	cmax = 0
	cmin = float('inf')
	req = defaultdict(lambda : 0)
	bal = 0
	for j in range(n):
		cmax = max(cmax, a[j])
		cmin = min(cmin, a[j])
		(x, y) = (req[b[j]], req[a[j]])
		if x == 0:
			bal += 1
		if y == 0:
			bal += 1
		req[b[j]] += 1
		req[a[j]] -= 1
		(x, y) = (req[b[j]], req[a[j]])
		if x == 0:
			bal -= 1
		if y == 0:
			bal -= 1
		if bal == 0:
			ans += cmax - cmin
			cmax = 0
			cmin = float('inf')
	print(ans)


import heapq
import sys
import math
from collections import deque
from bisect import bisect_left, bisect_right
I = sys.stdin.readline
II = lambda : int(I())
IN = lambda x: map(int, x.split())
FN = lambda x: map(float, x.split())
L = lambda x: list(IN(x))
M = 1000000007
P = print
T = True
F = False
for _ in range(II()):
	n = II()
	a = L(I())
	l = sorted(a)
	i = 0
	s = 0
	while i < n:
		while i < n and a[i] == l[i]:
			i += 1
		if i == n:
			break
		m = l[i]
		mc = 1
		x = i
		while i < n:
			if a[i] > m:
				m = a[i]
				mc = 1
			elif a[i] == m:
				mc += 1
			if l[i] == m:
				mc -= 1
			if mc == 0:
				break
			i += 1
		s += l[i] - l[x]
		i += 1
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	array = [int(i) for i in input().split()]
	sorted_array = sorted(array)
	flag = 1
	for i in range(n):
		if sorted_array[i] != array[i]:
			flag = 0
	if flag:
		print(0)
		continue
	position_dictionary = {}
	for index in range(n):
		position_dictionary[sorted_array[index]] = index
	left = 0
	while array[left] == sorted_array[left]:
		left += 1
	right = n - 1
	while array[right] == sorted_array[right]:
		right -= 1
	ans = 0
	l = left
	r = right
	while l <= r:
		maximum_array = array[l]
		minimu_array = array[l]
		pos_max = position_dictionary[array[l]]
		while l <= pos_max:
			if array[l] > maximum_array:
				maximum_array = array[l]
				pos_max = position_dictionary[maximum_array]
			if array[l] < minimu_array:
				minimu_array = array[l]
			l += 1
		ans += maximum_array - minimu_array
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().strip().split()]
	s_arr = sorted(arr)
	if s_arr == arr:
		print(0)
	else:
		pos_dict = {}
		for (index, i) in enumerate(s_arr):
			pos_dict[i] = index
		left = 0
		while arr[left] == s_arr[left]:
			left += 1
		right = n - 1
		while arr[right] == s_arr[right]:
			right -= 1
		ans = 0
		l = left
		r = right
		while l <= r:
			max_elem = arr[l]
			min_elem = arr[l]
			pos_max = pos_dict[arr[l]]
			while l <= pos_max:
				if arr[l] > max_elem:
					max_elem = arr[l]
					pos_max = pos_dict[max_elem]
				if arr[l] < min_elem:
					min_elem = arr[l]
				l += 1
			ans += max_elem - min_elem
		print(ans)


import sys, os, io
import math
from collections import defaultdict

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
res = []

def rec(i, j, rev, s):
	if i > j:
		return
	global res
	if rev == 0:
		res.append(s[j])
		rec(i, j - 1, 1, s)
	else:
		res.append(s[i])
		rec(i + 1, j, 0, s)

def printNSE(arr, n):
	s = []
	mp = {}
	s.append(arr[0])
	ans = []
	for i in range(1, n):
		if len(s) == 0:
			s.append(arr[i])
			continue
		while len(s) != 0 and s[-1] > arr[i]:
			mp[s[-1]] = arr[i]
			s.pop()
		s.append(arr[i])
	while len(s) != 0:
		mp[s[-1]] = -1
		s.pop()
	for i in range(n):
		print(arr[i], '--->', mp[arr[i]])

def solve():
	n = ii()
	l = li()
	d = defaultdict(lambda : 0)
	pp = -1
	new = sorted(l)
	i = 0
	while i < n:
		if l[i] == new[i]:
			i += 1
			continue
		pp = i
		i = n
	i = 0
	while i < n:
		d[l[i]] = i
		i += 1
	ppp = -1
	res = 0
	for i in range(n):
		if l[i] != new[i] or ppp != -1:
			if ppp != -1:
				ab = 1
			else:
				pp = i
			ppp = max(ppp, d[l[i]], d[new[i]])
			if i != ppp:
				continue
			xx = l[pp:ppp + 1]
			xx.sort()
			l[pp:ppp + 1] = xx
			x = l[ppp]
			y = l[pp]
			res += x - y
			ppp = -1
	print(res)
t = 1
t = ii()
for _ in range(t):
	solve()


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
sys.setrecursionlimit(3 * 10 ** 5)
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
x = 0
pref = []
lvl = []
gp = []
ans = []
f = 0
w = []

def hnbhai(tc):
	n = sb()
	a = sd()
	b = a.copy()
	b.sort()
	if a == b:
		print(0)
		return
	i = 0
	ans = 0
	mx = 0
	mn = float('inf')
	while i < n:
		mx = max(mx, a[i])
		mn = min(mn, a[i])
		if mx == b[i] and (i + 1 >= n or (i + 1 < n and b[i + 1] > b[i])):
			ans += mx - mn
			mx = 0
			mn = float('inf')
			i += 1
			continue
		i += 1
	print(ans)
	return
for _ in range(sb()):
	hnbhai(_ + 1)


import math, bisect, heapq, random, sys, itertools
(Y, N) = ('yes', 'no')
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p = 10 ** 9 + 7
for t in range(int(input())):
	(n,) = ints()
	a = ints()
	b = sorted(a)
	x = -1
	store = {}
	ans = 0
	for i in range(n):
		if b[i] not in store:
			store[b[i]] = []
		store[b[i]].append(i)
	for i in store:
		store[i] = store[i][::-1]
	(minn, maxx) = (p, 0)
	for i in range(n):
		y = store[a[i]].pop()
		x = max(x, y)
		minn = min(minn, a[i])
		maxx = max(maxx, a[i])
		if x == i:
			ans += maxx - minn
			minn = p
			maxx = 0
	print(ans)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = sorted(arr)
	visited = set()
	m = float('inf')
	g = -float('inf')
	ans = 0
	seen = Counter()
	i = 0
	while i < n:
		el = arr[i]
		p = d[i]
		seen[el] += 1
		seen[p] -= 1
		m = min(m, el, p)
		g = max(g, el, p)
		if el in visited and seen[el] == 0:
			visited.remove(el)
		if p in visited and seen[p] == 0:
			visited.remove(p)
		if seen[el]:
			visited.add(el)
		if seen[p]:
			visited.add(p)
		if len(visited) == 0:
			ans += g - m
			m = float('inf')
			g = -float('inf')
		i += 1
	print(ans)


import heapq as hq
from collections import deque

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	p = list()
	q = deque()
	ans = 0
	c = -1
	for (x, y) in zip(a, b):
		if len(q) == 0:
			c = y
		hq.heappush(p, x)
		q.append(y)
		while p and p[0] == q[0]:
			hq.heappop(p)
			q.popleft()
		if len(q) == 0:
			ans += y - c
	print(ans)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


from os import cpu_count
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import log, gcd
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
for _ in range(int(input())):
	N = int(input())
	A = li()
	right = [A[i] for i in range(N)]
	for i in range(N - 1)[::-1]:
		right[i] = min(right[i], right[i + 1])
	right.append(10 ** 9)
	A.append(10 ** 9)
	res = 0
	L = 0
	M = A[0]
	for i in range(N):
		if max(M, A[i]) <= right[i + 1]:
			res += max(A[L:i + 1]) - min(A[L:i + 1])
			L = i + 1
			M = A[i + 1]
		else:
			M = max(M, A[i])
	print(res)