Read problems statements in Mandarin Chinese  and Russian. 

Recently Chef has decided to make some changes in our beloved Codechef. As you know, each problem at Codechef has its memory and time limits. To make problems even more challenging, he decided to measure allocated memory in a different way. Now judge program will be calculating not the maximum memory usage during the execution of all test files, but all the memory ever allocated by the solution program. But as Chef is not that good in algorithms, so he asks you to write a program that will calculate total memory usage of a solution.
So, you are given N numbers M_{1}, , ,M_{N} representing the measurements of consumed memory (in MBs) for N test files. In other terms, it means that on i-th test file, program took M_{i} MBs of memory. Initially, there is no memory allocated for your program. Before running your program on each test file, if the currently allocated memory is more than memory needed for the current test file, then there will be a deallocation of the memory to fit the current program. Also, if there is less than needed memory available, then allocation of memory will happen so as to fit the current program. e.g. Let us say that our program took 10 MBs on current test file. So, assuming if there was 12 MBs memory allocated before running the program on current test file, then there will happen a deallocation of 2 MBs. Assuming if there was 8 MBs memory allocated before running the program on current test file, then there will happen a allocation of 2 MBs.

Calculate the total memory allocated for running the solution program on all the N test files. Please see third sample for more clarity.

------ Input ------ 

First line of input contains a single integer T denoting the  number of test cases. First line of each test case contains a single integer N denoting the number of measurements. Second line of each test case contains N space separated integers, where i^{th} integer denotes the consumption of memory for i^{th} i-th test file.

------ Output ------ 

For each test case, print total memory allocated for running the solution program.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ M_{i} ≤ 10^{9}$
$ sum of N over all test cases does not exceed 10^{5}$

------ Subtasks ------ 

Subtask 1 (30 points):

1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ M_{i} ≤ 100

Subtask 3 (70 points): 

Original constraints.

----- Sample Input 1 ------ 
3
2
1 1
5
1 2 3 4 5
3
1 3 2
----- Sample Output 1 ------ 
1
5
3
----- explanation 1 ------ 
Example case 1. Initially, there was no memory allocated. For running first test file, there was a memory allocation of 1 MBs. There was no allocation/ deallocation for running your program on second test file. 
Example case 2. On running on each test file, there was a further allocation of 1 MBs from previous one. So, there are total 5 MBs of memory allocated while running the program.
Example case 3. Initially, there was no memory allocated. For running first test file, there was a memory allocation of 1 MBs. For running second test file, there was a further memory allocation of 2 MBs to have 3 MBs of memory needed, then in the last file, there was a deallocation of 1 MB of memory so as to get 2 MBs of memory needed for running the program. So, overall, there was 1 + 2 = 3 MBs of memory ever allocated in the program. Note that we are only counting allocated memory, not allocated + unallocated.

Source: codechef | Difficulty: EASY
Tags: Data structures

Implementation


Solutions:
for i in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	m = l[0]
	m1 = max(l)
	for i in range(n - 1):
		if l[i + 1] - l[i] > 0:
			m = m + (l[i + 1] - l[i])
	print(max(m, m1))


T = int(input())
for _ in range(T):
	N = int(input())
	S = list(map(int, input().split()))
	s = [0] + S
	final = []
	for i in range(len(s) - 1):
		a = s[i + 1] - s[i]
		if a > 0:
			final.append(a)
	print(sum(final))


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


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


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


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


for t in range(int(input())):
	n = int(input())
	Listy = list(map(int, input().split()))
	count = Listy[0]
	current_mem = Listy[0]
	for i in range(0, len(Listy)):
		if Listy[i] > current_mem:
			count += Listy[i] - current_mem
			current_mem = Listy[i]
		elif Listy[i] < current_mem:
			current_mem = Listy[i]
	print(count)


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


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = [l[0]]
	f = l[0]
	for i in range(1, len(l)):
		if l[i] > f:
			d.append(l[i] - f)
			f = l[i]
		else:
			d.append('-' + str(int(f - l[i])))
			f = l[i]
	print(sum([i for i in d if type(i) == int]))


for _ in range(int(input())):
	n = int(input())
	mi = list(map(int, input().strip().split()))
	ext_req_al = 0
	re_mem = 0
	for i in mi:
		if i >= re_mem:
			ext_req_al += i - re_mem
		re_mem += i - re_mem
	print(ext_req_al)


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


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


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


t = int(input())
for _ in range(t):
	n = int(input())
	m = list(map(int, input().split()))
	lis = []
	lis.append(m[0])
	for i in range(len(m) - 1):
		if m[i + 1] > m[i]:
			lis.append(m[i + 1] - m[i])
	print(sum(lis))


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


for _ in range(int(input())):
	K = int(input())
	R = list(map(int, input().split()))
	S = 0
	p = R[0]
	for i in range(len(R) - 1):
		if R[i + 1] > R[i]:
			S = S + (R[i + 1] - R[i])
		else:
			exit
	print(p + S)


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


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	allo = 0
	curmem = 0
	for ele in arr:
		if ele > curmem:
			allo += ele - curmem
		curmem = ele
	print(allo)


for _ in range(int(input())):
	n = int(input())
	m = [int(x) for x in input().split()]
	ans = m[0]
	for i in range(1, n):
		ans += max([m[i] - m[i - 1], 0])
	print(ans)


a = int(input(''))
for i in range(a):
	x = int(input(''))
	t = [int(x) for x in input('').split()]
	k = list(t)
	l = []
	for j in range(0, len(k) - 1):
		if k[j + 1] - k[j] > 0:
			l.append(k[j + 1] - k[j])
	print(k[0] + sum(l))


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


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	allo = []
	count = 0
	for i in a:
		if i == count:
			allo.append(0)
		elif i < count:
			allo.append(0)
		else:
			allo.append(i - count)
		count = i
	print(sum(allo))


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	c = 0
	for j in range(len(A) - 1):
		if A[j + 1] >= A[j]:
			P = A[j + 1] - A[j]
			c += P
	print(A[0] + c)


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


t = int(input())
while t > 0:
	x = int(input())
	l = list(map(int, input().split()))
	current = 0
	sum = 0
	for i in range(len(l)):
		if i == 0:
			current = l[0]
			sum = l[0]
		elif l[i] > current:
			sum += l[i] - current
			current = l[i]
		else:
			current = l[i]
	print(sum)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	res = maxi = lst[0]
	for i in range(1, n):
		if lst[i] > maxi:
			res += lst[i] - maxi
			maxi += lst[i] - maxi
		else:
			maxi -= maxi - lst[i]
	print(res)


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


t = int(input())
for i in range(t):
	n = int(input())
	data = [int(d) for d in input().split()]
	sum = data[0]
	for j in range(1, n):
		if data[j] > data[j - 1]:
			value = data[j] - data[j - 1]
			sum += value
		else:
			sum += 0
	print(sum)


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


t = int(input())
for ni in range(t):
	n = int(input())
	m = [int(i) for i in input().split()]
	count = m[0]
	for i in range(1, n):
		if m[i] > m[i - 1]:
			count = count + m[i] - m[i - 1]
	print(count)


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


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	m = l[0]
	for i in range(1, n):
		if l[i] > l[i - 1]:
			m += l[i] - l[i - 1]
	print(m)


for x in range(int(input())):
	n = int(input())
	a = [int(d) for d in input().split()]
	summ = a[0]
	for i in range(1, n):
		if a[i] > a[i - 1]:
			summ += a[i] - a[i - 1]
	print(summ)


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


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	count = l[0]
	prev = l[0]
	for i in range(a - 1):
		if l[i + 1] - l[i] > 0:
			count += l[i + 1] - l[i]
	print(count)


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


T = int(input())
for t in range(T):
	N = int(input())
	arr = [int(ele) for ele in input().split()]
	smallAns = arr[0]
	for i in range(1, N):
		if arr[i] > arr[i - 1]:
			smallAns += arr[i] - arr[i - 1]
	print(smallAns)


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


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	total = 0
	cur = 0
	for i in range(n):
		if arr[i] > total:
			cur += abs(arr[i] - total)
			total = arr[i]
		elif arr[i] < total:
			total = arr[i]
	print(cur)


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


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	sum = l[0]
	for j in range(1, n):
		if l[j] > l[j - 1]:
			value = l[j] - l[j - 1]
			sum += value
		else:
			sum += 0
	print(sum)


testcase = int(input())
for i in range(testcase):
	n = int(input())
	arr = list(map(int, input().split()))
	al = 0
	t = 0
	for i in arr:
		if i >= t:
			al += i - t
			t += i - t
		else:
			t += i - t
	print(al)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = l[0]
	for i in range(1, n):
		if l[i] > l[i - 1]:
			ans += l[i] - l[i - 1]
	print(ans)


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


t = int(input())
for _ in range(t):
	n = int(input())
	lis = list(map(int, input().split()))
	s = 0
	ans = 0
	for i in range(n):
		if i == 0:
			s += lis[i]
			ans += lis[i]
		elif lis[i] < s:
			x = s - lis[i]
			s = s - x
		elif lis[i] > s:
			x = lis[i] - s
			ans += x
			s = s + x
	print(ans)


for i in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	c = 0
	for j in range(n - 1):
		if A[j + 1] >= A[j]:
			P = A[j + 1] - A[j]
			c += P
	print(A[0] + c)


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


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


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


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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	al = 0
	t = 0
	for i in a:
		if i >= t:
			al += i - t
			t += i - t
		else:
			t += i - t
	print(al)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = 0
	c = 0
	for i in range(n):
		if l[i] > t:
			c += abs(l[i] - t)
			t = l[i]
		elif l[i] < t:
			t = l[i]
	print(c)


t = int(input())
for tc in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = l[0]
	sum = l[0]
	for j in range(1, n):
		if l[j] > m:
			sum += l[j] - m
		m = l[j]
	print(sum)


for i in range(int(input())):
	a = int(input())
	l = [int(i) for i in input().split()]
	s = l[0]
	for i in range(1, a):
		if l[i] > l[i - 1]:
			val = l[i] - l[i - 1]
			s += val
		else:
			s += 0
	print(s)


for t in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	ans = l[0]
	for i in range(1, n):
		if l[i] > l[i - 1]:
			ans += l[i] - l[i - 1]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	tm = 0
	for i in range(n):
		if i == 0:
			tm += l[i]
		else:
			alloc = l[i] - l[i - 1]
			if alloc > 0:
				tm += alloc
	print(tm)


T = int(input())
for i in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	count = A[0]
	for j in range(n - 1):
		if A[j + 1] - A[j] > 0:
			count = count + (A[j + 1] - A[j])
	print(count)


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


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


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	curMem = a[0]
	s = a[0]
	for i in range(1, len(a)):
		if curMem < a[i]:
			s = s + (a[i] - curMem)
			curMem = a[i]
		else:
			curMem = a[i]
	print(s)


for t in range(int(input())):
	n = int(input())
	li = [int(x) for x in input().split()]
	x = 0
	alloc = 0
	p = 0
	for i in li:
		p = i - x
		if p > 0:
			alloc += p
		x = i
	print(alloc)