There are N stones in a pond, each having a value A_{i} written on it. A frog is at stone 1 and wants to reach stone N. The frog can jump from a stone i to any stone j (j>i). Let d be the length of subarray (i.e. j-i+1), then the energy required for the jump is (d \cdot A_{i})-A_{j}. Find the minimum non-negative amount of energy required by the frog to reach the N-th stone.

Note: It is possible that the total amount of energy required is negative, in that case, you should print the minimum non-negative value (i.e. 0).

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

- The first line contains an integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the number of stones.
- The second line contains N integers denoting the numbers written on the stones.

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

For each test case output a single integer - the minimum non-negative energy required by the frog.

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

$ 1 ≤T ≤2500 $ - the number of test cases
$ 1 ≤N ≤10^{5} $ - the number of stones.
$ 1 ≤A_{i} ≤10^{9} $ - the number written on stones.
- Sum of $N$ over all test cases does not exceed $5 \cdot 10^{5} $

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

Subtask 1 (5 points): $1 ≤N ≤10, 1 ≤A_{i} ≤100, \sum N ≤50$
Subtask 2 (10 points): $1 ≤N ≤100, 1 ≤A_{i} ≤100, \sum N ≤500$
Subtask 3 (15 points): $1 ≤N ≤1000, \sum N ≤5000$
Subtask 4 (70 points): original constraints

----- Sample Input 1 ------ 
4
3
6 1 3
4
3 1 10 4
3
7 9 1
2
1 5
----- Sample Output 1 ------ 
10
4
20
0
----- explanation 1 ------ 
- Test Case $1$: The frog can jump to the $2^{nd}$ stone from the $1^{st}$ stone, and then to the $3^{rd}$ stone from the $2^{nd}$ stone.
- Test Case $3$: The frog can jump to the $3^{rd}$ stone directly from the $1^{st}$ stone.
- Test Case $4$: The frog can jump to the $2^{nd}$ stone from the $1^{st}$ stone. However, the energy required in this case is negative (i.e. $-3$), So we will print $0$.

Difficulty: VERY_HARD
Tags: Dynamic programming

Data structures

Greedy algorithms
Skill types: Dynamic programming

Data structures

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	stones = list(map(int, input().split()))
	ans = n * stones[0] - stones[-1]
	jumps = [0]
	val = 0
	for i in range(1, n):
		if stones[i] <= stones[jumps[-1]]:
			val += (i - jumps[-1] + 1) * stones[jumps[-1]] - stones[i]
			jumps.append(i)
	if jumps[-1] != n - 1:
		val += (n - jumps[-1]) * stones[jumps[-1]] - stones[-1]
	print(max(0, min(val, ans)))


def subArrayJump(n, arr):
	e = 0
	st = 1
	for idx in range(1, n):
		if arr[st - 1] > arr[idx] or idx == n - 1:
			x = (idx - st + 2) * arr[st - 1] - arr[idx]
			e = e + x
			st = idx + 1
	return max(0, e)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	print(subArrayJump(n, arr))


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	ans = 0
	minn = s[0]
	for i in range(n):
		ans += minn
		minn = min(minn, s[i])
	print(max(ans - s[-1], 0))


import sys
import math
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	i = 0
	j = 1
	while j < n:
		if arr[j] > arr[i] and j != n - 1:
			j += 1
		else:
			ans += arr[i] * (j - i + 1) - arr[j]
			i = j
			j += 1
	print(max(0, ans))


t = int(input())
while t > 0:
	n = int(input())
	lst = list(map(int, input().split()))
	energy = 0
	i = 0
	for j in range(n - 1):
		if lst[i] > lst[j]:
			energy += (j - i + 1) * lst[i] - lst[j]
			i = j
	energy += (n - 1 - i + 1) * lst[i] - lst[n - 1]
	print(max(energy, 0))
	t -= 1


t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	e = 0
	if n != 1:
		d = 1
		i = 1
		p = a[0]
		while i < n:
			if p > a[i]:
				d += 1
				e += d * p - a[i]
				d = 1
				p = a[i]
			else:
				d += 1
				if i == n - 1:
					e += d * p - a[i]
			i += 1
	if e < 0:
		e = 0
	print(e)


import math
t = int(input())
while t != 0:
	n = int(input())
	stones = list(map(int, input().split()))
	prev = 0
	min_energy = 0
	for i in range(1, n):
		if stones[i] < stones[prev] or i == n - 1:
			min_energy += (i - prev + 1) * stones[prev] - stones[i]
			prev = i
	print(max(0, min_energy))
	t -= 1


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


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	if N == 1:
		print(0)
	else:
		ans = 2 * A[0] - A[-1]
		temp = A[0]
		for i in range(1, N - 1):
			if A[i] >= temp:
				ans += temp
			else:
				ans += A[i]
				temp = A[i]
		print(max(0, ans))


from typing import DefaultDict
from math import sqrt
import math

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def prime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n
for _ in range(int(input())):
	bool = True
	ans = 0
	n = int(input())
	l = list(map(int, input().split()))
	new = []
	temp = l[0]
	if n == 1:
		print(0)
	elif n == 2:
		print(max(2 * l[0] - l[1], 0))
	else:
		for i in range(n):
			if i == n - 1:
				new.append([l[i], i])
			elif l[i] <= temp:
				new.append([l[i], i])
				temp = l[i]
		for i in range(len(new) - 1):
			ans += new[i][0] * (new[i + 1][1] - new[i][1] + 1)
			ans -= new[i + 1][0]
		print(max(0, ans))


get_int = lambda : int(input())
get_list_int = lambda : list(map(int, input().split()))
t = get_int()
for t_itr in range(t):
	n = get_int()
	arr = get_list_int()
	ans = 0
	prev = 0
	for i in range(1, n):
		if i == n - 1 or arr[i] <= arr[prev]:
			ans += (i - prev + 1) * arr[prev] - arr[i]
			prev = i
	print(max(0, ans))


def solve(arr, n):
	energy = 0
	curr_cost = arr[0]
	last_step = 1
	last_completed = False
	for i in range(n):
		last_completed = False
		if curr_cost > arr[i]:
			energy += curr_cost * (i + 1 - last_step + 1) - arr[i]
			curr_cost = arr[i]
			last_step = i + 1
			last_completed = True
	if not last_completed:
		energy += curr_cost * (n + 1 - last_step) - arr[-1]
	return max(energy, 0)
t = int(input())
for _ in range(t):
	n = int(input())
	stones = [int(x) for x in input().split()]
	print(solve(stones, n))


from math import *
for u in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(x, y) = (0, 0)
	s = 0
	while y < n:
		if l[y] >= l[x]:
			y = y + 1
		else:
			s += (y - x + 1) * l[x] - l[y]
			x = y
	s += (n - x) * l[x] - l[n - 1]
	if s <= 0:
		print(0)
	else:
		print(s)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	energy = 0
	lp = 0
	rp = 0
	while rp < N:
		if A[rp] >= A[lp]:
			rp += 1
		else:
			energy += (rp - lp + 1) * A[lp] - A[rp]
			lp = rp
	energy += (N - lp) * A[lp] - A[N - 1]
	if energy <= 0:
		print(0)
	else:
		print(energy)


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


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	if n == 1:
		print(0)
	elif n == 2:
		ans = 2 * x[0] - x[1]
	elif n > 2:
		ans = 2 * x[0] - x[-1]
		temp = x[0]
		for i in range(1, n - 1):
			if temp <= x[i]:
				ans += temp
			elif temp > x[i]:
				ans += x[i]
				temp = x[i]
	print(max(0, ans))


from sys import stdin, stdout
write = stdout.write
input = stdin.readline
for t in range(int(input())):
	n = int(input())
	A = list(map(int, input().strip().split()))
	dp = [0]
	(mindp, minx) = (0, 0)
	for i in range(1, n):
		temp = float('inf')
		for j in (mindp, minx):
			temp = min(temp, dp[j] + ((i - j + 1) * A[j] - A[i]))
		if dp[i - 1] <= dp[mindp]:
			mindp = i
		if A[i] <= A[minx]:
			minx = i
		dp.append(temp)
	print(max(0, dp[-1]))


def I():
	return input().strip()

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import sys, os, copy, string, math, time, functools, fractions
input = sys.stdin.readline
from io import BytesIO, IOBase
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, chain, combinations, groupby
from operator import itemgetter
from types import GeneratorType
from typing import Iterable, TypeVar, Union

def main():
	n = II()
	a = LI()
	if n == 1:
		print(0)
	else:
		final = 0
		last = 0
		for i in range(1, n - 1):
			if a[i] > a[last]:
				continue
			final += (i - last + 1) * a[last] - a[i]
			last = i
		final += (n - 1 - last + 1) * a[last] - a[-1]
		print(max(final, 0))
for _ in range(II()):
	main()


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	dp = [float('inf') for i in range(n)]
	all = [0]
	last = a[0]
	for i in range(1, n):
		if a[i] < last:
			all.append(i)
			last = a[i]
	if all[-1] != n - 1:
		all.append(n - 1)
	ans = 0
	p = len(all)
	for i in range(p - 1):
		first = all[i]
		second = all[i + 1]
		ans += (second - first + 1) * a[first] - a[second]
	print(max(0, ans))