Omkar is building a waterslide in his water park, and he needs your help to ensure that he does it as efficiently as possible.

Omkar currently has $n$ supports arranged in a line, the $i$-th of which has height $a_i$. Omkar wants to build his waterslide from the right to the left, so his supports must be nondecreasing in height in order to support the waterslide. In $1$ operation, Omkar can do the following: take any contiguous subsegment of supports which is nondecreasing by heights and add $1$ to each of their heights. 

Help Omkar find the minimum number of operations he needs to perform to make his supports able to support his waterslide!

An array $b$ is a subsegment of an array $c$ if $b$ can be obtained from $c$ by deletion of several (possibly zero or all) elements from the beginning and several (possibly zero or all) elements from the end.

An array $b_1, b_2, \dots, b_n$ is called nondecreasing if $b_i\le b_{i+1}$ for every $i$ from $1$ to $n-1$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 100$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of supports Omkar has.

The second line of each test case contains $n$ integers $a_{1},a_{2},...,a_{n}$ $(0 \leq a_{i} \leq 10^9)$ — the heights of the supports.

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


-----Output-----

For each test case, output a single integer — the minimum number of operations Omkar needs to perform to make his supports able to support his waterslide.


-----Example-----
Input
3
4
5 3 2 5
5
1 2 3 5 3
3
1 1 1

Output
3
2
0



-----Note-----

The subarray with which Omkar performs the operation is bolded.

In the first test case:

First operation:

$[5, 3, \textbf{2}, 5] \to [5, 3, \textbf{3}, 5]$

Second operation:

$[5, \textbf{3}, \textbf{3}, 5] \to [5, \textbf{4}, \textbf{4}, 5]$

Third operation:

$[5, \textbf{4}, \textbf{4}, 5] \to [5, \textbf{5}, \textbf{5}, 5]$

In the third test case, the array is already nondecreasing, so Omkar does $0$ operations.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())

    out = 0
    l = list(map(int, input().split()))
    for i in range(n - 1):
        out += max(0, l[i] - l[i + 1])
    print(out)


def f(arr):
    d = max(arr)
    for i in range(len(arr)):
        arr[i] = d - arr[i]


# for _ in range(1):
for _ in range(int(input())):
    # n, k = map(int, input().split())
    n = int(input())
    arr = list(map(int, input().split()))
    i = n - 1
    ans = 0
    while i > 0:
        if arr[i - 1] <= arr[i]:
            i -= 1
            continue
        ans += arr[i - 1] - arr[i]
        i -= 1
    print(ans)

t=int(input())
for i in range(t):
    n=int(input())
    a=list(map(int, input().split()))
    s=0
    for i in range(n-1):
       if a[i]>a[i+1]:
           s=s+a[i]-a[i+1]
    print(s)



import sys
from collections import defaultdict
t=1
t=int(input())
for i in range(t):
    n=int(input())
    # lenn=len(n)
    a=list(map(int,sys.stdin.readline().strip().split()))
    # b=list(map(int,sys.stdin.readline().strip().split()))
    # a,b,c,d=list(sys.stdin.readline().strip().split())
    # n,k=list(map(int,sys.stdin.readline().strip().split()))
    
    # f=1
    # for j in range(n-1):
    #     if(a[j]==a[j+1]):
    #         continue
    #     f=0
    # if(f):
    #     print(n)
    # else:
    #     print(1)
    
    op=0
    for j in range(1,n):
        if(a[j]>a[j-1]):
            continue
        else:
            op+=a[j-1]-a[j]
    print(op)

T = int(input())
for _ in range(T):
    N = int(input())
    A = [int(a) for a in input().split()]
    print(sum([max(A[i] - A[i+1], 0) for i in range(N - 1)]))


from sys import exit,stdin,stderr
def rl():
    return [int(w) for w in stdin.readline().split()]

T, = rl()
for _ in range(T):
    n, = rl()
    a = rl()
    r = 0
    for i in range(n - 1):
        d = a[i] - a[i+1]
        if d > 0:
            r += d
    print(r)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))

	t = 0
	for i in range(1, n):
		if a[i] < a[i-1]:
			t += a[i-1]-a[i]
	print(t)

t=int(input())
for you in range(t):
    n=int(input())
    l=input().split()
    li=[int(i) for i in l]
    curr=0
    for i in range(1,n):
        if(li[i]<li[i-1]):
            curr=curr+(li[i-1]-li[i])
    print(curr)


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    ans=0
    for i in range(1,n):
        if a[i]<a[i-1]:
            ans+=a[i-1]-a[i]
    print(ans)

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(1, n):
        ans += max(a[i - 1] - a[i], 0)
    print(ans)

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

t = int(input())
for _ in range(t):
    n = int(input())
    l1 = [int(x) for x in input().split()]
    ans = 0
    for i in range(n):
        if i==0:
            old = l1[0]
        else:
            if old>l1[i]:
                ans+=old-l1[i]
                old = l1[i]
            else:
                old = l1[i]
    print(ans)


def solve():
    n = int(input())
    lst = list(map(int,input().split()))
    lst.reverse()
    ans = 0
    for i in range(1, n):
        if lst[i-1] < lst[i]:
            ans += lst[i] - lst[i-1]
    print(ans)
for i in range(int(input())):
    solve()

for _ in range(int(input())):
    x = int(input())
    Ans = 0
    A = list(map(int, input().split()))
    for i in range(x - 1):
        if A[i] > A[i + 1]:
            Ans += A[i] - A[i + 1]
    print(Ans)

import sys
input = sys.stdin.readline
for f in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    sol=0
    for i in range(1,n):
        if a[i]<a[i-1]:
            sol+=a[i-1]
            sol-=a[i]
    print(sol)

from collections import defaultdict as dd
import math
import sys
input=sys.stdin.readline
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))


def solve():
	n=nn()
	nums = lm()
	needed = 0
	for i in reversed(list(range(1,n))):
		if nums[i]<nums[i-1]:
			needed+= nums[i-1]-nums[i]

	print(needed)

q=nn()
for _ in range(q):
	solve()



from sys import stdin

tt = int(stdin.readline())

for loop in range(tt):

    n = int(stdin.readline())
    a = list(map(int,stdin.readline().split()))

    ans = 0
    for i in range(n-1):
        ans += max(0 , a[i] - a[i+1])
    print (ans)

t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(j) for j in input().split()]
	ans = 0
	ind = n-2
	while ind != -1:
		while ind != -1 and arr[ind]<=arr[ind+1]:
			ind -= 1

		if ind != -1:
			ans += arr[ind]-arr[ind+1]
			arr[ind+1] = arr[ind]

	print(ans)


import sys
input = sys.stdin.readline


t=int(input())
for tests in range(t):
    n=int(input())
    A=list(map(int,input().split()))

    M=[A[0]]
    for a in A[1:]:
        M.append(max(M[-1],a))

    A.append(M[-1])

    #print(M)

    ANS=0
    for i in range(n):
        if A[i]>A[i+1]:
            continue
        else:
            ANS+=min(M[i],A[i+1])-A[i]

    print(ANS)
    


for _ in range(int(input())):
    n = int(input())
    a = [0]+[*list(map(int,input().split()))]
    d = [0]*(n+1)
    for i in range(1,n+1):
        d[i]=a[i]-a[i-1]
    s = 0
    i = 1
    while(i<=n):
        if(d[i]>=0):
            i+=1
            continue
        mn = d[i]
        while(i+1<=n and d[i+1]<0):
            i+=1
            mn += d[i]
        s += (-1)*mn
        i+=1
    print(s)