Read problem statements in [Hindi],[Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

As usual, I went to work in the morning. Unfortunately, I found out that my manager bought a new machine and I have to learn to operate it.

There are $N$ boxes in a line (numbered $1$ through $N$). Initially, the boxes are empty, and I need to use the machine to put tokens in them. For each valid $i$, the $i$-th box has a maximum capacity $S_{i}$ tokens. I can perform the following operation any number of times: choose an integer $L$ ($1 ≤ L ≤ N$) and put one token in each of the boxes $1, 2, \ldots, L$.

My manager told me to put as many tokens as possible into the boxes in total (the distribution of tokens in the boxes does not matter). Of course, it is not allowed to perform an operation that would result in the number of tokens in some box exceeding its capacity. Can you help me calculate the maximum number of tokens that can be put in these boxes?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $S_{1}, S_{2}, \ldots, S_{N}$.

------  Output ------
For each test case, print a single line containing one integer - the maximum number of tokens.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{6}$
$1 ≤ S_{i} ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{6}$

------  Subtasks ------
Subtask #1 (50 points):
$1 ≤ N ≤ 1,000$
$1 ≤ S_{i} ≤ 1,000$ for each valid $i$
the sum of $N$ over all test cases does not exceed $5,000$

Subtask #2 (50 points): original constraints

----- Sample Input 1 ------ 
1

3

2 1 3
----- Sample Output 1 ------ 
4
----- explanation 1 ------ 
Example case 1: The optimal way is to perform the following operations:
- Choose $L = 3$ and use the machine to put one token in each box.
- Choose $L = 1$ and use the machine to put one more token in the first box.

Difficulty: MEDIUM
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	s = 0
	while len(l) > 0:
		d = min(l)
		ans = ans + (d - s) * len(l)
		s = d
		l = l[:l.index(d)]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	s = 0
	while len(a) > 0:
		d = min(a)
		ans += (d - s) * len(a)
		s = d
		a = a[:a.index(d)]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().lstrip().split()))
	(ans, mini) = (0, float('inf'))
	for i in arr:
		mini = min(mini, i)
		ans += mini
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	(ans, mini) = (0, float('inf'))
	for i in a:
		mini = min(mini, i)
		ans += mini
	print(ans)


for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	j = 0
	sum1 = list1[j]
	minval = list1[j]
	while j < n - 1:
		if list1[j + 1] <= list1[j]:
			if minval > list1[j + 1]:
				minval = list1[j + 1]
				sum1 += minval
			else:
				sum1 += minval
		elif minval > list1[j + 1]:
			minval = list1[j + 1]
			sum1 += minval
		else:
			sum1 += minval
		j += 1
	print(sum1)


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


for j in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	e = 0
	mn = 10 ** 9
	mn += 1
	for g in range(n):
		if k[g] < mn:
			e = g
			mn = k[g]
	sm = 0
	for y in range(e):
		sm += k[y] - mn
	sm += mn * n
	print(sm)


t = int(input())
for i in range(0, t):
	n = int(input())
	s = list(map(int, input().split()))
	temp = s[0]
	total = 0
	for i in s:
		temp = min(temp, i)
		total = total + temp
	print(total)


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	res = 0
	temp = s[0]
	for i in s:
		temp = min(temp, i)
		res += temp
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	temp = []
	minimum = l[0]
	for i in l:
		if i <= minimum:
			minimum = i
			temp.append(minimum)
		else:
			temp.append(minimum)
	print(sum(temp))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ind = n
	c = 0
	m = min(a)
	while a[0] != 0:
		for i in range(ind):
			a[i] -= m
			c += m
		ind = a.index(0)
		if ind == 0:
			break
		m = min(a[:ind])
	print(c)


def get_s(s, min):
	for i in range(len(s)):
		if s[i] == min:
			s = s[:i]
			break
	return s

def reduce_s(s, min):
	for i in range(len(s)):
		s[i] -= min
	return s
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	ans = 0
	while s:
		m = min(s)
		ans += m * len(s)
		s = get_s(s, m)
		s = reduce_s(s, m)
	print(ans)


def solve(arr):
	ans = 0
	temp = arr[0]
	for i in arr:
		temp = min(temp, i)
		ans += temp
	return ans
for _ in range(int(input())):
	a = int(input())
	print(solve(list(map(int, input().split()))))


def solve(arr):
	ans = 0
	stack = []
	for (i, j) in enumerate(arr):
		if not stack:
			stack = [i + 1, j]
		elif stack[1] <= j:
			stack = [i + 1, stack[1]]
		else:
			ans += stack[0] * (stack[1] - j)
			stack = [i + 1, j]
	return ans + stack[0] * stack[1]
for _ in range(int(input())):
	a = int(input())
	print(solve(list(map(int, input().split()))))


def solve(arr):
	ans = 0
	stack = []
	for (i, j) in enumerate(arr):
		if not stack:
			stack.append([i + 1, j])
		else:
			temp = stack.pop()
			if temp[1] <= j:
				stack.append([i + 1, temp[1]])
			else:
				temp[1] -= j
				stack.append(temp)
				stack.append([i + 1, j])
	for (x, y) in stack:
		ans += x * y
	return ans
for _ in range(int(input())):
	a = int(input())
	print(solve(list(map(int, input().split(' ')))))


t = int(input())
for _ in range(t):
	input()
	arr = [int(x) for x in input().strip().split()]
	minArr = [arr[0]]
	for value in arr[1:]:
		minArr.append(min(minArr[-1], value))
	print(sum(minArr))


import sys
t = int(input())
while t > 0:
	n = int(input())
	s = input().strip().split()
	a = [int(s[i]) for i in range(n)]
	m = sys.maxsize
	ans = 0
	for i in range(n):
		m = min(m, a[i])
		ans += m
	print(ans)
	t -= 1


import operator
for i in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	ans = 0
	m = min(s)
	b = 0
	x = 0
	while True:
		if len(s) == 1:
			ans += (s[0] - b) * len(s)
			break
		if len(s) == 0:
			break
		(x, r) = min(enumerate(s), key=operator.itemgetter(1))
		ans += (r - b) * len(s)
		b = r
		s = s[:x]
	print(ans)


for i in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	ans = 0
	m = min(s)
	b = 0
	x = 0
	while True:
		if len(s) == 1:
			ans += (s[0] - b) * len(s)
			break
		if len(s) == 0:
			break
		r = min(s)
		x = s.index(r)
		ans += (r - b) * len(s)
		b = r
		s = s[:x]
	print(ans)


import numpy as np
t = int(input())
for i in range(t):
	N = int(input())
	array = list(map(int, input().split()))
	array = np.array(array)
	count = 0
	min = 999999999
	for j in range(N):
		if array[j] < min:
			min = array[j]
			count += min
		else:
			count += min
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	(m, c) = (s[0], 0)
	for i in s:
		if i < m:
			m = i
		c = c + m
	print(c)


for _ in range(int(input())):
	a = input()
	l = list(map(int, input().split()))
	(r, m) = (0, l[0])
	for i in l:
		if i < m:
			m = i
		r += m
	print(r)


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

	def mini(a):
		x = min(a)
		for i in range(len(a) - 1, -1, -1):
			if a[i] == x:
				return i
	ans = 0
	while len(a):
		x = mini(a)
		y = min(a)
		ans += len(a) * y
		a = a[:x]
		for i in range(len(a)):
			a[i] -= y
	print(ans)


numTest = int(input())
for _ in range(numTest):
	input()
	arr = list(map(int, input().split()))
	(res, minn) = (0, arr[0])
	for i in arr:
		if i < minn:
			minn = i
		res += minn
	print(res)


n = int(input())
while n:
	num = int(input())
	total = 0
	count = 0
	l = list(map(int, input().split()))
	total += l[0]
	mini = l[0]
	for i in range(1, len(l)):
		if l[i] < mini:
			mini = l[i]
			total += mini
		else:
			total += mini
	print(total)
	n -= 1


t = int(input())
for i in range(t):
	n = int(input())
	S = list(map(int, input().split()))
	i = S.index(min(S))
	p = 0
	for j in range(i + 1):
		p += S[j]
	print(p + (len(S) - i - 1) * S[i])


from heapq import *

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	pq = []
	for (i, a) in enumerate(arr):
		heappush(pq, [a, i])
	(j, ans, prev) = (n, 0, 0)
	while j > 0 and pq:
		(cur, i) = heappop(pq)
		if i < j and cur - prev > 0:
			ans += (cur - prev) * j
			prev = cur
			j = i
	return ans
for _ in range(int(input())):
	print(solve())


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


for i in range(int(input())):
	num = int(input())
	arr = list(map(int, input().split()))
	total = arr[0]
	ans = 0
	for j in range(num):
		total = min(total, arr[j])
		ans += total
	print(ans)


for _ in range(int(input())):
	N = int(input())
	S = list(map(int, input().split()))
	i = S.index(min(S))
	p = 0
	for j in range(i + 1):
		p += S[j]
	print(p + (len(S) - i - 1) * S[i])


for _ in range(int(input())):
	n = int(input())
	s = [int(x) for x in input().strip().split()]
	minArr = [s[0]]
	for value in s[1:]:
		minArr.append(min(minArr[-1], value))
	print(sum(minArr))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [x for x in map(int, input().split())]
	m = a[0]
	res = m
	for i in range(1, n):
		m = min(m, a[i])
		res += m
	print(res)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	mn = float('inf')
	for j in range(n):
		mn = min(mn, arr[j])
		ans += mn
	print(ans)


try:
	T = int(input())
	while T > 0:
		N = int(input())
		S = list(map(int, input().strip().split()))
		(s, m) = (0, S[0])
		for i in S:
			m = min(m, i)
			s += m
		print(s)
except:
	pass


try:
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		(s, m) = (0, l[0])
		for i in l:
			m = min(m, i)
			s += m
		print(s)
except:
	pass


def solve():
	n = int(input())
	lis = list(map(int, input().split()))
	ans = lis[0]
	Min = ans
	for i in range(1, n):
		Min = min(Min, lis[i])
		ans += Min
	print(ans)
for _ in range(int(input())):
	solve()


def solve():
	n = int(input())
	lis = list(map(int, input().split()))
	Min = min(lis)
	ans = Min * n
	ind = -1
	for i in range(n):
		if lis[i] == Min:
			ind = i
			break
	for i in range(ind):
		if lis[i] > Min:
			ans += lis[i] - Min
	print(ans)
for _ in range(int(input())):
	solve()


def solve():
	n = int(input())
	lis = list(map(int, input().split()))
	ans = 0
	M = min(lis)
	ans = M * n
	ind = -1
	for i in range(n):
		if lis[i] == M:
			ind = i
			break
	for i in range(ind):
		if lis[i] > M:
			ans += lis[i] - M
		else:
			break
	print(ans)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	low = 1000000000.0
	for i in arr:
		low = min(low, i)
		ans += low
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	S = list(map(int, input().split()))
	Min = Sum = S[0]
	for i in range(1, N):
		Min = min(Min, S[i])
		Sum += Min
	print(Sum)


for _ in range(int(input())):
	(n, l, m, s) = (int(input()), list(map(int, input().split())), 10000000000, 0)
	for i in l:
		if i < m:
			m = i
		s += m
	print(s)


t = int(input())
for i in range(t):
	z = int(input())
	a = list(map(int, input().split()))
	(res, mini) = (a[0], a[0])
	for j in range(1, z):
		if a[j] < mini:
			mini = a[j]
			res += mini
		else:
			res += mini
	print(res)


k = int(input())
for _ in range(k):
	N = int(input())
	li = list(map(int, input().split()))
	count = 0
	m = li[0]
	for i in range(len(li)):
		m = min(m, li[i])
		count += m
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = l[0]
	c = 0
	for j in range(n):
		s = min(s, l[j])
		c += s
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	abcd = arr1[0]
	ans = 0
	for i in range(n):
		abcd = min(abcd, arr1[i])
		ans += abcd
	print(ans)


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


for t in range(int(input())):
	N = int(input())
	S = list(map(int, input().split()))
	minimum = [S[0]]
	for i in range(1, N):
		if S[i] < minimum[-1]:
			minimum.append(S[i])
		else:
			minimum.append(minimum[-1])
	print(sum(minimum))


try:
	for t in range(int(input())):
		N = int(input())
		S = list(map(int, input().split()))
		minimum = [S[0]]
		for i in range(1, N):
			if S[i] < minimum[-1]:
				minimum.append(S[i])
			else:
				minimum.append(minimum[-1])
		curr = 0
		curr += minimum[-1] * len(S)
		for i in range(N - 2, -1, -1):
			if minimum[i] > minimum[i + 1]:
				curr += (minimum[i] - minimum[i + 1]) * (i + 1)
		print(curr)
except:
	pass


for t in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	ans = 0
	mini = max(li)
	for i in range(n):
		if i - 1 > -1:
			mini = min(li[i], mini)
		else:
			mini = li[i]
		ans += mini
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	mn = arr[0]
	ans = 0
	for i in range(n):
		mn = min(mn, arr[i])
		ans += mn
	print(ans)


try:
	for _ in range(int(input())):
		N = int(input())
		S = list(map(int, input().split()))
		m = S[0]
		T = 0
		for i in S:
			if i < m:
				m = i
			T += m
		print(T)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	mn = arr[0]
	ans = 0
	for i in range(n):
		mn = min(mn, arr[i])
		ans += mn
	print(ans)


testcases = int(input())
for _ in range(testcases):
	t = int(input())
	arr = list(map(int, input().split()))
	maxelement = arr[0]
	maxenv = 0
	for i in range(0, len(arr)):
		if maxelement == arr[i]:
			maxenv += arr[i]
		elif maxelement > arr[i]:
			maxelement = arr[i]
			maxenv += arr[i]
		else:
			maxenv += maxelement
	print(maxenv)


for i in range(int(input())):
	r = int(input())
	l = list(map(int, input().split()))
	x = l[0]
	c = 0
	for i in l:
		if i < x:
			x = i
		c += x
	print(c)


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


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	key = l[0]
	c = 0
	for i in l:
		if i < key:
			key = i
		c = c + key
	print(c)


import sys
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	min_int = sys.maxsize
	c = 0
	for i in range(0, len(l)):
		min_int = min(min_int, l[i])
		c += min_int
	print(c)


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


import sys
for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	mi = sys.maxsize
	ans = 0
	for i in range(0, len(li)):
		mi = min(mi, li[i])
		ans += mi
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = a[0]
	y = 0
	for j in a:
		if j < m:
			m = j
		y += m
	print(y)


for _ in range(int(input())):
	machine = int(input())
	st = [int(k) for k in input().split()]
	h = st[0]
	i = 0
	for k in range(machine):
		if st[k] < h:
			h = st[k]
		i += h
	print(i)


for _ in range(int(input())):
	machine = int(input())
	stu = [int(k) for k in input().split()]
	m = stu[0]
	i = 0
	for k in range(machine):
		if stu[k] < m:
			m = stu[k]
		i += m
	print(i)


for _ in range(int(input())):
	n = int(input())
	lit = [int(i) for i in input().split()]
	m = lit[0]
	x = 0
	for i in range(n):
		if lit[i] < m:
			m = lit[i]
		x += m
	print(x)


for _ in range(int(input())):
	nahi = int(input())
	lst = [int(i) for i in input().split()]
	m = lst[0]
	x = 0
	for i in range(nahi):
		if lst[i] < m:
			m = lst[i]
		x += m
	print(x)


import sys
for t in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	res = sys.maxsize
	c = 0
	for i in range(0, len(s)):
		res = min(res, s[i])
		c = c + res
	print(c)