Little Dormi received a histogram with $n$ bars of height $a_1, a_2, \ldots, a_n$ for Christmas. However, the more he played with his new histogram, the more he realized its imperfections, so today he wanted to modify it to his liking.

To modify the histogram, Little Dormi is able to perform the following operation an arbitrary number of times:

Select an index $i$ ($1 \le i \le n$) where $a_i>0$, and assign $a_i := a_i-1$.

Little Dormi defines the ugliness score of his histogram (after performing some number of operations) as the sum of the vertical length of its outline and the number of operations he performed on it. And to make the histogram as perfect as possible, he would like to minimize the ugliness score after modifying it with some number of operations.

However, as his histogram is very large, Little Dormi is having trouble minimizing the ugliness score, so as Little Dormi's older brother, help him find the minimal ugliness.

Consider the following example where the histogram has $4$ columns of heights $4,8,9,6$:

The blue region represents the histogram, and the red lines represent the vertical portion of the outline. Currently, the vertical length of the outline is $4+4+1+3+6 = 18$, so if Little Dormi does not modify the histogram at all, the ugliness would be $18$.

However, Little Dormi can apply the operation once on column $2$ and twice on column $3$, resulting in a histogram with heights $4,7,7,6$:

Now, as the total vertical length of the outline (red lines) is $4+3+1+6=14$, the ugliness is $14+3=17$ dollars. It can be proven that this is optimal.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 4 \cdot 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$).

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


-----Output-----

For each test case output one integer, the minimal ugliness Little Dormi can achieve with the histogram in that test case.


-----Examples-----

Input
2
4
4 8 9 6
6
2 1 7 4 0 0
Output
17
12


-----Note-----

Example $1$ is the example described in the statement.

The initial histogram for example $2$ is given below:

The ugliness is currently $2+1+6+3+4=16$.

By applying the operation once on column $1$, six times on column $3$, and three times on column $4$, we can end up with a histogram with heights $1,1,1,1,0,0$:

The vertical length of the outline is now $1+1=2$ and Little Dormi made $1+6+3=10$ operations, so the final ugliness is $2+10=12$, which can be proven to be optimal.

Difficulty: EASY
Tags: Mathematics

Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
k = int(input())
for i in range(k):
	n = int(input())
	l = list(map(int, input().split()))
	an = 0
	o = 0
	p = 0
	if n == 1:
		print(l[0])
		continue
	for i in range(n):
		if i == 0 and l[0] > l[1]:
			an += l[0] - l[1]
			l[0] = l[1]
		if i > 0 and i < n - 1:
			if l[i] > l[i - 1] and l[i] > l[i + 1]:
				an += l[i] - max(l[i - 1], l[i + 1])
				l[i] = max(l[i - 1], l[i + 1])
			an += abs(l[i] - l[i - 1])
		if i == n - 1 and l[n - 1] > l[n - 2]:
			an += l[n - 1] - l[n - 2]
			l[n - 1] = l[n - 2]
	an += l[0]
	an += l[n - 1]
	an += abs(l[n - 1] - l[n - 2])
	print(an)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
from array import array
import heapq
import math
sys.setrecursionlimit(100000)
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def test_case():
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr = [0] + arr + [0]
	ans = 0
	for i in range(1, n + 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			ans += arr[i] - max(arr[i - 1], arr[i + 1])
			arr[i] = max(arr[i - 1], arr[i + 1])
	for i in range(n + 1):
		ans += abs(arr[i] - arr[i + 1])
	print(ans)

def main():
	t = int(input())
	for _ in range(t):
		test_case()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
main()

def dummy_function():
	x = 10
	x *= 100
	print('This function is written by Harsh.')

def dummy_function1():
	x = 10
	x *= 100
	print('This function is written by Harsh.')

def dummy_function3():
	x = 10
	x *= 100
	print('This function is written by Harsh.')

def dummy_function4():
	x = 10
	x *= 100
	print('This function is written by Harsh.')


def readline():
	return map(int, input().split())

def solve():
	n = int(input())
	seq = list(readline())
	seq.extend([0, 0])
	ans = 0
	(a, b) = (0, 0)
	for c in seq:
		if a < b > c:
			diff = b - max(a, c)
			ans += diff
			b -= diff
		ans += abs(b - a)
		(a, b) = (b, c)
	print(ans)

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


for s in [*open(0)][2::2]:
	a = (0, *map(int, s.split()), 0)
	print(sum((abs(x - y) + abs(y - z) - 2 * min(max(0, y - x), max(0, y - z)) for (x, y, z) in zip(a, a[1:], a[2:]))) + a[1] + a[-2] >> 1)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(item) for item in input().split()]
	arr2 = [0]
	arr2.extend(arr)
	arr2.extend([0])
	countops = 0
	for i in range(1, len(arr2) - 1):
		if arr2[i - 1] < arr2[i] and arr2[i + 1] < arr2[i]:
			diff = min(arr2[i] - arr2[i - 1], arr2[i] - arr2[i + 1])
			arr2[i] = arr2[i] - diff
			countops += diff
	count = 0
	for i in range(len(arr2) - 1):
		count += abs(arr2[i + 1] - arr2[i])
	print(count + countops)


t = int(input())
for _ in range(t):
	n = int(input())
	columns = tuple(map(int, input().split()))
	columns = (0, *columns, 0)
	ugliness = 0
	for i in range(1, n + 1):
		smaller_neighbor = min(columns[i - 1], columns[i + 1])
		if columns[i - 1] < columns[i] > columns[i + 1]:
			larger_neighbor = max(columns[i - 1], columns[i + 1])
			ugliness += columns[i] - larger_neighbor
			ugliness += larger_neighbor - smaller_neighbor
			continue
		if columns[i] - smaller_neighbor > 0:
			ugliness += columns[i] - smaller_neighbor
	print(ugliness)


t = int(input())

def main():
	n = int(input())
	heights = list(map(int, input().split(' ')))
	ugliness = 0
	for (i, h) in enumerate(heights):
		left_h = 0 if i == 0 else heights[i - 1]
		right_h = 0 if i == n - 1 else heights[i + 1]
		left_d = h - left_h
		right_d = h - right_h
		left_u = 0 if left_d < 0 else left_d
		right_u = 0 if right_d < 0 else right_d
		ugliness += left_u + right_u - min(left_u, right_u)
	print(ugliness)
for _ in range(t):
	main()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(arr[0])
	else:
		s = arr[0] + arr[-1]
		for i in range(n - 1):
			s += abs(arr[i] - arr[i + 1])
		l = []
		if arr[0] > arr[1]:
			s -= abs(arr[1] - arr[0])
		if arr[-1] > arr[-2]:
			s -= abs(arr[-1] - arr[-2])
		for i in range(1, n - 1):
			if arr[i - 1] < arr[i] > arr[i + 1]:
				l.append(i)
		for i in l:
			s -= abs(arr[i] - max(arr[i - 1], arr[i + 1]))
		print(s)


t = int(input())
answers = list()
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if i == 0:
			prev = 0
		else:
			prev = a[i - 1]
		if i == n - 1:
			next_ = 0
			ans += a[i]
		else:
			next_ = a[i + 1]
		curr = a[i]
		ans += abs(curr - prev)
		if curr > prev and curr > next_:
			ans -= min(abs(curr - prev), abs(curr - next_))
	answers.append(ans)
for k in range(t):
	print(answers[k])


import sys
import io, os
import math
gcd = math.gcd
ceil = math.ceil
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def print(x, end='\n'):
	sys.stdout.write(str(x) + end)

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		arr = [0] + arr + [0]
		lis = [0] * (n + 1)
		if n == 1:
			print(arr[1])
			continue
		for i in range(n + 1):
			lis[i] = arr[i + 1] - arr[i]
		c = 0
		for i in range(n + 1):
			c += abs(lis[i])
		for i in range(n):
			prev = lis[i]
			nex = lis[i + 1]
			if prev > 0 and nex < 0:
				c -= min(abs(prev), abs(nex))
		print(c)
main()


t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(a[0])
	else:
		cnt = 0
		if a[0] > a[1]:
			cnt += a[0] - a[1]
			a[0] = a[1]
		for i in range(1, n - 1):
			q = max(a[i - 1], a[i + 1])
			if a[i] > q:
				cnt += a[i] - q
				a[i] = q
		if a[n - 1] > a[n - 2]:
			cnt += a[n - 1] - a[n - 2]
			a[n - 1] = a[n - 2]
		cnt += a[0] + a[n - 1]
		for i in range(n - 1):
			cnt += abs(a[i] - a[i + 1])
		print(cnt)


def histogramUgliness(n, histogram):
	histogram = [0] + histogram + [0]
	operations = 0
	ans = 0
	for x in range(1, n + 1):
		if histogram[x] > histogram[x - 1] and histogram[x] > histogram[x + 1]:
			f = max(histogram[x - 1], histogram[x + 1])
			operations += histogram[x] - f
			histogram[x] = f
	for x in range(0, n + 1):
		ans += abs(histogram[x] - histogram[x + 1])
	return ans + operations
t = int(input())
final = []
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	final.append(histogramUgliness(n, l))
for _ in range(t):
	print(final[_])


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	d = 0
	if n == 1:
		d += a[0]
		a[0] = 0
	for i in range(n):
		if i > 0:
			if i < n - 1:
				if a[i - 1] < a[i] > a[i + 1]:
					d += a[i] - max(a[i - 1], a[i + 1])
					a[i] = max(a[i - 1], a[i + 1])
			elif a[i] > a[i - 1]:
				d += a[i] - a[i - 1]
				a[i] = a[i - 1]
		elif i < n - 1:
			if a[i] > a[i + 1]:
				d += a[i] - a[i + 1]
				a[i] = a[i + 1]
	dif = []
	p = 0
	for i in a:
		dif.append(i - p)
		p = i
	dif.append(-a[n - 1])
	print(sum((abs(i) for i in dif)) + d)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	n = inp()
	l = li()
	if n == 1:
		pr(l[0])
		return
	(a, b, c) = (0, 0, 0)
	for i in range(n):
		if not i:
			if l[i] > l[i + 1]:
				c += l[i] - l[i + 1]
				b += 2 * (l[i] - l[i + 1])
			a += l[i]
		elif i == n - 1:
			if l[i] > l[i - 1]:
				c += l[i] - l[i - 1]
				b += 2 * (l[i] - l[i - 1])
			a += l[i]
		else:
			if l[i] > l[i - 1] and l[i] > l[i + 1]:
				c += l[i] - max(l[i - 1], l[i + 1])
				b += 2 * (l[i] - max(l[i - 1], l[i + 1]))
			a += abs(l[i] - l[i - 1])
	a += abs(l[-2] - l[-1])
	pr(a + c - b)
for _ in range(inp()):
	solve()


t = int(input())
for x in range(t):
	n = int(input())
	liczby = list(map(int, input().split()))
	zabrane = 0
	if n > 1:
		for z in range(n - 2):
			if liczby[z + 1] > liczby[z] and liczby[z + 1] > liczby[z + 2]:
				if liczby[z] >= liczby[z + 2]:
					zabrane = zabrane + (liczby[z + 1] - liczby[z])
					liczby[z + 1] = liczby[z]
				else:
					zabrane = zabrane + (liczby[z + 1] - liczby[z + 2])
					liczby[z + 1] = liczby[z + 2]
		if liczby[0] > liczby[1]:
			zabrane = zabrane + (liczby[0] - liczby[1])
			liczby[0] = liczby[1]
		if liczby[len(liczby) - 1] > liczby[len(liczby) - 2]:
			zabrane = zabrane + (liczby[len(liczby) - 1] - liczby[len(liczby) - 2])
			liczby[len(liczby) - 1] = liczby[len(liczby) - 2]
	liczba = liczby[0]
	for y in range(n - 1):
		liczba = liczba + abs(liczby[y + 1] - liczby[y])
	if n > 1:
		liczba = liczba + liczby[len(liczby) - 1]
	print(liczba + zabrane)


def is_peak(hist, index):
	if hist[index] <= hist[index - 1]:
		return 0
	if hist[index] <= hist[index + 1]:
		return 0
	return hist[index] - max(hist[index - 1], hist[index + 1])

def solve():
	n = int(input())
	hist_heights = [0] + [int(x) for x in input().split()] + [0]
	relative_hegihts = [0] * len(hist_heights)
	for i in range(1, n + 2):
		relative_hegihts[i] = hist_heights[i] - hist_heights[i - 1]
	ugliness = sum((abs(i) for i in relative_hegihts))
	for i in range(1, n + 1):
		delta_height = is_peak(hist_heights, i)
		if delta_height > 0:
			ugliness -= delta_height
	return ugliness
for _ in range(int(input().strip())):
	print(solve())


import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, sys
from sys import stdin, stdout

def modinv(n, p):
	return pow(n, p - 2, p)

def nc():
	return map(int, ns().split())

def narr():
	return list(map(int, ns().split()))

def ns():
	return input()

def ni():
	return int(input())
t = ni()
for _ in range(t):
	n = ni()
	a = narr()
	ans = 0
	ugg = 0
	if n == 1:
		ans = a[0]
	else:
		ugg = a[0] + a[n - 1]
		for i in range(1, n):
			ugg += abs(a[i] - a[i - 1])
		for i in range(n):
			if (i == 0 or a[i - 1] < a[i]) and (i == n - 1 or a[i] > a[i + 1]):
				ops = 2000000000
				if i > 0:
					ops = min(ops, a[i] - a[i - 1])
				if i < n - 1:
					ops = min(ops, a[i] - a[i + 1])
				ans += ops
				ugg -= 2 * ops
	print(ans + ugg)


t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, str(input()).split()))
	cou = 0
	if n == 1:
		print(ar[0])
		continue
	for i in range(n):
		if i == 0:
			if ar[0] > ar[i + 1]:
				cou += ar[0] - ar[1]
				ar[0] = ar[i + 1]
		elif i == n - 1:
			if ar[i] > ar[i - 1]:
				cou += ar[i] - ar[i - 1]
				ar[i] = ar[i - 1]
		elif ar[i] > ar[i - 1] and ar[i] > ar[i + 1]:
			c = max(ar[i - 1], ar[i + 1])
			cou += ar[i] - c
			ar[i] = c
	ans = ar[0] + ar[n - 1]
	for i in range(0, n - 1):
		ans += abs(ar[i] - ar[i + 1])
	print(cou + ans)


for _ in range(int(input())):
	safd = input()
	l = [int(i) for i in input().split()]
	s = 0
	if len(l) == 1:
		print(l[0])
	else:
		for i in range(len(l)):
			a = 0
			b = 0
			if i + 1 < len(l):
				a = l[i + 1]
			if i - 1 >= 0:
				b = l[i - 1]
			maxi = max(a, b)
			if l[i] < maxi:
				pass
			else:
				s += abs(maxi - l[i])
				l[i] = maxi
		v = l[0]
		for i in range(1, len(l)):
			v += abs(l[i] - l[i - 1])
		v += l[i]
		print(v + s)


for _ in range(int(input())):
	(n, m) = (int(input()), 0)
	l = [0] + [*map(int, input().split())] + [0]
	for i in range(1, n + 2):
		if l[i - 1] < l[i] > l[i + 1]:
			m += l[i] - max(l[i - 1], l[i + 1])
			l[i] = max(l[i - 1], l[i + 1])
	print(sum((abs(l[i] - l[i - 1]) for i in range(1, n + 2))) + m)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(a[0])
	elif n == 2:
		print(2 * min(a) + abs(a[0] - a[1]))
	else:
		ans = a[0] + a[-1]
		for i in range(1, n):
			ans += abs(a[i - 1] - a[i])
		if a[0] > a[1]:
			ans -= a[0] - a[1]
		if a[-1] > a[-2]:
			ans -= a[-1] - a[-2]
		for i in range(1, n - 1):
			if a[i] > a[i - 1] and a[i] > a[i + 1]:
				ans -= min(a[i] - a[i - 1], a[i] - a[i + 1])
		print(ans)


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


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


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


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(ugl, prev, fact, temp) = (arr[-1], 0, 0, 0)
	for i in arr:
		ugl += abs(prev - i)
		if i - prev < 0 and fact > 0:
			temp += min(prev - i, fact)
		fact = i - prev
		prev = i
	if fact > 0:
		temp += min(prev - 0, fact)
	print(ugl - temp)


aa = int(input())
for g in range(aa):
	n = int(input())
	m = list(map(int, input().split(' ')))
	doing = 0
	if n == 1:
		print(m[0])
		continue
	for i in range(n):
		if i == 0:
			if m[0] > m[1]:
				doing += m[0] - m[1]
				m[0] = m[1]
				continue
		if i == n - 1:
			if m[n - 1] > m[n - 2]:
				doing += m[n - 1] - m[n - 2]
				m[n - 1] = m[n - 2]
				continue
		if m[i] > m[i - 1] and m[i] > m[i + 1]:
			doing += m[i] - max(m[i + 1], m[i - 1])
			m[i] = max(m[i + 1], m[i - 1])
	res = m[0] + doing
	for i in range(1, n):
		res += abs(m[i] - m[i - 1])
	res += m[-1]
	print(res)


iter = int(input())
for iters in range(iter):
	n = int(input())
	array = [int(i) for i in input().split(' ')]
	if n == 1:
		print(array[0])
		continue
	original_cost = 0
	optimizable_cost = 0
	original_cost = array[0]
	if array[0] > array[1]:
		optimizable_cost = array[0] - array[1]
	for j in range(1, n - 1):
		a = array[j - 1]
		b = array[j]
		c = array[j + 1]
		original_cost += abs(a - b)
		if b > max(a, c):
			optimizable_cost += b - max(a, c)
	b = array[n - 1]
	a = array[n - 2]
	original_cost += abs(a - b)
	original_cost += b
	if b > a:
		optimizable_cost += b - a
	print(original_cost - optimizable_cost)


def f(a):
	a = [0] + a + [0]
	ans = 0
	for i in range(1, len(a) - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			ans += a[i] - max(a[i + 1], a[i - 1])
			a[i] = max(a[i + 1], a[i - 1])
	for i in range(1, len(a)):
		ans += abs(a[i] - a[i - 1])
	return ans
for _ in range(int(input())):
	l = input()
	a = list(map(int, input().strip().split()))
	print(f(a))


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


def ugli(list, n):
	if n == 1:
		return list[0]
	else:
		a = list[0]
		for i in range(1, n):
			if list[i] - list[i - 1] > 0:
				a += list[i] - list[i - 1]
			else:
				a += list[i - 1] - list[i]
		a += list[-1]
		return a
t = int(input())
for i in range(t):
	n = int(input())
	list = [int(i) for i in input().split()]
	a = ugli(list, n)
	if n == 1:
		print(a)
	else:
		if list[0] > list[1]:
			a -= list[0] - list[1]
		if list[-1] > list[-2]:
			a -= list[-1] - list[-2]
			list[-1] = list[-2]
		for i in range(1, n - 1):
			if list[i] > list[i - 1] and list[i] > list[i + 1]:
				a -= list[i] - max(list[i + 1], list[i - 1])
		print(a)


def solve(x):
	lst = []
	lst = [int(lst) for lst in input().split()]
	value = 0
	count = 0
	if len(lst) == 1:
		print(lst[0])
	else:
		for i in range(0, len(lst)):
			if i == 0:
				if lst[i + 1] < lst[i]:
					value = lst[i] - lst[i + 1]
					lst[i] = lst[i] - value
					count = count + value
				else:
					pass
			elif i > 0 and i < len(lst) - 1:
				if lst[i - 1] >= lst[i] and lst[i + 1] >= lst[i]:
					pass
				elif lst[i - 1] < lst[i] and lst[i + 1] < lst[i]:
					if lst[i - 1] > lst[i + 1]:
						value = 0
						value = lst[i] - lst[i - 1]
					else:
						value = 0
						value = lst[i] - lst[i + 1]
					lst[i] = lst[i] - value
					count = count + value
			elif i == len(lst) - 1:
				if lst[i] > lst[i - 1]:
					value = lst[i] - lst[i - 1]
					lst[i] = lst[i] - value
					count = count + value
		value = 0
		for i in range(0, len(lst)):
			if i == 0 or i == len(lst) - 1:
				count = count + lst[i]
				if i == 0 and lst[i] != lst[i + 1]:
					value = lst[i] - lst[i + 1]
					value = abs(value)
					count = count + value
			elif i >= 0 and i < len(lst) - 1:
				if lst[i] != lst[i + 1]:
					value = lst[i] - lst[i + 1]
					value = abs(value)
					count = count + value
		print(count)
		count = 0
		value = 0
testcase = int(input())
while testcase > 0:
	x = int(input())
	solve(x)
	testcase = testcase - 1


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


t = int(input())
for _ in range(t):
	n = int(input())
	l = [0] + list(map(int, input().split()))
	l.append(0)
	l.append(0)
	score = 0
	for i in range(1, n + 2):
		score += abs(l[i] - l[i - 1])
		if l[i - 1] < l[i] and l[i] > l[i + 1]:
			score -= min(l[i] - l[i - 1], l[i] - l[i + 1])
	print(score)


import sys
import os
if 'CP_LOCAL' in os.environ:
	sys.stdin = open('codeforces/input.txt', 'r')
	sys.stdout = open('codeforces/output.txt', 'w')
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def ugliness(arr):
	t = [0] + arr + [0]
	u = t[0]
	for i in range(1, len(t)):
		u += abs(t[i] - t[i - 1])
	return u

def solve(arr):
	u = ugliness(arr)
	temp = [0] + arr + [0]
	for i in range(1, len(temp) - 1):
		if temp[i - 1] < temp[i] > temp[i + 1]:
			u -= temp[i] - max(temp[i - 1], temp[i + 1])
	return u
T = inp()
for _ in range(T):
	n = inp()
	arr = inlt()
	print(solve(arr))


t = int(input())
for _ in range(t):
	input()
	a = list(map(int, input().split()))
	if len(a) == 1:
		ops = a[0]
		a[0] = 0
	else:
		ops = 0
		if a[0] > a[1]:
			ops += a[0] - a[1]
			a[0] = a[1]
		for i in range(1, len(a) - 1):
			if a[i - 1] < a[i] and a[i] > a[i + 1]:
				max_neighbor = max(a[i - 1], a[i + 1])
				ops += a[i] - max_neighbor
				a[i] = max_neighbor
		if a[-1] > a[-2]:
			ops += a[-1] - a[-2]
			a[-1] = a[-2]
	total_vertical = a[0]
	for i in range(1, len(a)):
		total_vertical += abs(a[i] - a[i - 1])
	total_vertical += a[-1]
	ugliness = ops + total_vertical
	print(ugliness)


def calc_uggliness(hist, operations=0):
	uggliness = operations
	for (i, x) in enumerate(hist[:-1]):
		uggliness += abs(x - hist[i + 1])
	return uggliness

def solve():
	n = int(input())
	hist = [0] + [int(x) for x in input().split()] + [0]
	uggliness = calc_uggliness(hist)
	for i in range(1, n + 1):
		if hist[i - 1] < hist[i] > hist[i + 1]:
			diff = hist[i] - max(hist[i - 1], hist[i + 1])
			uggliness -= diff
			hist[i] -= diff
	print(uggliness)
t = int(input())
for _ in range(t):
	solve()


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


t = int(input())
for tc in range(t):
	n = int(input())
	arr = [int(z) for z in input().split()]
	arr.insert(0, 0)
	arr.append(0)
	ugly = 0
	for i in range(1, len(arr)):
		ugly += abs(arr[i] - arr[i - 1])
	for i in range(1, len(arr) - 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			ugly -= arr[i] - max(arr[i + 1], arr[i - 1])
	print(ugly)


def solver(a):
	base_sum = 0
	sum = 0
	b_s = []
	s = []
	a = [0] + a + [0]
	for index in range(1, len(a) - 1):
		dl = a[index] - a[index - 1]
		dr = a[index] - a[index + 1]
		if dl > 0:
			base_sum += dl
			b_s.append(dl)
		if dr > 0:
			base_sum += dr
			b_s.append(dr)
		if dl > 0 and dr > 0:
			temp = min(dl, dr)
		else:
			temp = 0
		sum += temp
		s.append(temp)
	return base_sum - sum
t = int(input())
out = []
for _ in range(t):
	n = int(input())
	a = list(map(int, str(input()).split(' ')))
	out.append(solver(a))
print('\n'.join(map(str, out)))


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


def f(a):
	s = a[0] + a[-1]
	for i in range(1, len(a)):
		s += abs(a[i] - a[i - 1])
	return s
T = int(input())
for t in range(T):
	n = int(input())
	s = 0
	a = list(map(int, input().split()))
	a.insert(0, 0)
	a.append(0)
	for i in range(1, n + 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			k = a[i]
			a[i] = max(a[i - 1], a[i + 1])
			s += k - a[i]
	a.pop(0)
	a.pop(-1)
	print(f(a) + s)


import sys
from os import path
import bisect
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output1.txt', 'w')
from heapq import heappop, heappush, heapify
from math import ceil
maxi = sys.maxsize
mini = -maxi
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(l[0])
	else:
		uvalue = l[0]
		for i in range(1, n):
			uvalue += abs(l[i] - l[i - 1])
		uvalue += l[-1]
		uvalue -= max(0, l[0] - l[1])
		i = 1
		while i < n:
			if i == n - 1:
				uvalue -= max(0, l[-1] - l[-2])
			else:
				c = max(0, l[i] - max(l[i - 1], l[i + 1]))
				uvalue -= c
			i += 1
		print(uvalue)


for s in [*open(0)][2::2]:
	r = d = x = 0
	for y in map(int, s.split() + [0]):
		r -= min(max(0, x - y), max(0, d)) - abs((d := (y - x)))
		x = y
	print(r)


T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A = [0] + A + [0]
	p = 0
	for n in range(1, N + 2):
		p += abs(A[n] - A[n - 1])
	for n in range(1, N + 1):
		f = max(0, A[n] - max(A[n + 1], A[n - 1]))
		p -= f
	print(p)


import sys, math, bisect
from random import randint
inf = float('inf')
mod = 10 ** 9 + 7

def lcm(a, b):
	return int(a / math.gcd(a, b) * b)

def gcd(a, b):
	return int(math.gcd(a, b))

def tobinary(n):
	return bin(n)[2:]

def binarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def lowerBound(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def upperBound(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return -1

def primesInRange(n):
	ans = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def primeFactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n = n // i
	if n > 2:
		factors.append(n)
	return factors

def isPrime(n, k=5):
	if n < 2:
		return True
	for i in range(0, k):
		a = randint(1, n - 1)
		if pow(a, n - 1, n) != 1:
			return False
	return True
from collections import deque, defaultdict, Counter
import heapq, string
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.insert(0, 0)
	arr.append(0)
	cost = 0
	for i in range(1, n + 1):
		og = arr[i]
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			arr[i] = max(arr[i - 1], arr[i + 1])
			cost += og - arr[i]
	for i in range(1, n + 2):
		cost += abs(arr[i] - arr[i - 1])
	print(cost)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
for ik in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	l = [0] + l + [0]
	for i in range(1, len(l) - 1):
		if l[i] > l[i - 1] and l[i] > l[i + 1]:
			ans += l[i] - max(l[i - 1], l[i + 1])
			l[i] = max(l[i - 1], l[i + 1])
	for i in range(1, len(l)):
		ans += abs(l[i] - l[i - 1])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	init = a[0] + a[-1]
	if n != 1:
		for i in range(1, n):
			init += abs(a[i] - a[i - 1])
	if n == 1:
		print(init // 2)
	else:
		if a[0] > a[1]:
			init -= abs(a[0] - a[1])
			a[0] = a[1]
		if a[-1] > a[-2]:
			init -= abs(a[-1] - a[-2])
			a[-1] = a[-2]
		for i in range(1, n - 1):
			if a[i] > a[i - 1] and a[i] > a[i + 1]:
				init -= abs(a[i] - max(a[i - 1], a[i + 1]))
				a[i] = max(a[i - 1], a[i + 1])
		print(init)


n = int(input())
answers = []
for i in range(n):
	ans = 0
	n1 = int(input())
	a = input().split()
	a = [int(i) for i in a]
	a.insert(0, 0)
	a.append(0)
	for j in range(1, n1 + 1):
		ans += abs(a[j] - a[j - 1])
		if a[j] > a[j - 1] and a[j] > a[j + 1]:
			ans -= a[j] - max(a[j - 1], a[j + 1])
	ans += a[n1]
	answers.append(ans)
for i in range(n):
	print(answers[i])


def ugly(arr):
	n = len(arr)
	if n == 1:
		return arr[0]
	f = arr[0] - arr[1]
	less = 0
	if f > 0:
		less += f
	l = arr[-1] - arr[-2]
	if l > 0:
		less += l
	ug = 0
	for i in range(n - 1):
		ug += abs(arr[i] - arr[i + 1])
	ug += arr[0] + arr[-1]
	for i in range(1, n - 1):
		if arr[i - 1] < arr[i] and arr[i] > arr[i + 1]:
			less += min(arr[i] - arr[i - 1], arr[i] - arr[i + 1])
	return ug - less
t = int(input())
for i in range(t):
	input()
	arr = list(map(int, input().split()))
	print(ugly(arr))


import sys, os
if os.environ['USERNAME'] == 'kissz':
	inp = open('in.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = sys.stdin.readline

	def debug(*args):
		pass
for _ in range(int(inp())):
	n = int(inp())
	A = [0] + [*map(int, inp().split())] + [0, 0]
	s = 0
	for i in range(1, n + 2):
		s += abs(A[i] - A[i - 1])
		s -= max(0, A[i] - max(A[i - 1], A[i + 1]))
	print(s)


def task():
	n = int(input())
	a = list(map(int, input().split()))
	ur = 0
	ur = +a[0]
	for i in range(1, n):
		ur += abs(a[i] - a[i - 1])
	ur += a[n - 1]
	if n == 1:
		return ur - a[0]
	if a[0] > a[1]:
		ur -= a[0] - a[1]
		a[0] = a[1]
	for i in range(1, n - 1):
		cut = min(a[i] - a[i - 1], a[i] - a[i + 1])
		cut = max(0, cut)
		ur -= cut
		a[i] -= cut
	if a[-1] > a[-2]:
		ur -= a[-1] - a[-2]
		a[-1] = a[-2]
	return ur
t = int(input())
for _ in range(t):
	print(task())


for t in range(int(input())):
	n = int(input())
	L = [int(X) for X in input().split()]
	if n == 1:
		print(L[0])
	else:
		ans = L[0] + L[-1]
		for i in range(1, n):
			ans += abs(L[i] - L[i - 1])
		for i in range(n):
			if i == 0:
				if L[0] > L[1]:
					ans -= L[0] - L[1]
			elif i == n - 1:
				if L[n - 1] > L[n - 2]:
					ans -= L[n - 1] - L[n - 2]
			elif i != 0 or i != n - 1:
				if L[i] > L[i - 1] and L[i] > L[i + 1]:
					ans -= L[i] - max(L[i - 1], L[i + 1])
		print(ans)


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

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

def fi():
	return float(input())

def si():
	return input()

def msi():
	return map(str, input().split())

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

def li():
	return list(mi())

def lsi():
	return list(msi())

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	return x * y // gcd(x, y)
mod = 1000000007

def modInverse(b, m):
	g = gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def ceil2(x, y):
	if x % y == 0:
		return x // y
	else:
		return x // y + 1

def modu(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	if inv == -1:
		return -999999999
	else:
		return inv * a % m
from math import log, factorial, cos, tan, sin, radians, floor, sqrt, ceil, log2
import bisect
import random
import string
from decimal import *
getcontext().prec = 50
abc = 'abcdefghijklmnopqrstuvwxyz'
pi = 3.141592653589793

def gcd1(a):
	if len(a) == 1:
		return a[0]
	ans = a[0]
	for i in range(1, len(a)):
		ans = gcd(ans, a[i])
	return ans

def mykey(x):
	return len(x)

def checkper_sq(n):

	def check(n, mod):
		for i in range(mod):
			if i * i % mod == n % mod:
				return True
		return False
	for i in range(3, 101):
		if not check(n, i):
			return False
	return True

def main():
	for _ in range(ii()):
		n = ii()
		a = li()
		if n == 1:
			print(a[0])
			continue
		ans = 0
		for i in range(n):
			if i == 0:
				if a[i] > a[i + 1]:
					x = a[i] - a[i + 1]
					a[i] -= x
					ans += x
			elif i == n - 1:
				if a[i] > a[i - 1]:
					x = a[i] - a[i - 1]
					a[i] -= x
					ans += x
			else:
				y = max(a[i + 1], a[i - 1])
				if a[i] > y:
					x = a[i] - y
					a[i] -= x
					ans += x
		for i in range(n):
			if i == 0:
				ans += a[i]
			elif i == n - 1:
				ans += a[n - 1]
				ans += max(a[i - 1], a[i]) - min(a[i - 1], a[i])
			else:
				ans += max(a[i - 1], a[i]) - min(a[i - 1], a[i])
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os, sys, math
from io import BytesIO, IOBase
from collections import defaultdict, deque, OrderedDict
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(input())

def In():
	return map(int, input().split())

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

def Sn():
	return input().strip()
BUFSIZE = 8192

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return len(a)

def solve():
	n = I()
	l = list(In())
	total = 0
	for i in range(n):
		if i == 0:
			total += l[i]
		else:
			total += abs(l[i] - l[i - 1])
			if i == n - 1:
				total += l[i]
	ans = 0
	for i in range(n):
		if i == 0:
			if i + 1 < n and l[i + 1] < l[i]:
				ans += l[i] - l[i + 1]
				l[i] = l[i + 1]
		elif i == n - 1:
			if i - 1 >= 0 and l[i - 1] < l[i]:
				ans += l[i] - l[i - 1]
				l[i] = l[i - 1]
		elif l[i] > l[i - 1] and l[i] > l[i + 1]:
			t = max(l[i - 1], l[i + 1])
			ans += l[i] - t
			l[i] = t
	print(total - ans)
	pass

def main():
	T = I()
	for i in range(T):
		solve()
M = 998244353
P = 1000000007

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def solve(arr) -> int:
	n = len(arr)
	left = [0] * n
	right = [0] * n
	for i in range(len(arr)):
		if i == 0:
			left[i] = arr[i]
			if i == n - 1:
				right[i] = arr[i]
			else:
				right[i] = max(0, arr[i] - arr[i + 1])
		elif i == n - 1:
			right[i] = arr[i]
			left[i] = max(0, arr[i] - arr[i - 1])
		else:
			left[i] = max(0, arr[i] - arr[i - 1])
			right[i] = max(0, arr[i] - arr[i + 1])
	res = 0
	for i in range(n):
		res += max(left[i], right[i])
	return res
for _ in range(int(input())):
	input()
	arr = list(map(int, input().split()))
	print(solve(arr))


for _ in range(int(input())):
	n = int(input())
	arr = [0] + list(map(int, input().split())) + [0]
	p = [(max(arr[i] - arr[i - 1], 0), max(arr[i] - arr[i + 1], 0)) for i in range(1, n + 1)]
	k = 0
	for elem in p:
		k += elem[0] + elem[1] - min(elem[0], elem[1])
	print(k)


for s in [*open(0)][2::2]:
	r = c = x = 0
	for y in map(int, s.split() + [0]):
		t = abs((d := (y - x)))
		r += max(t - c, (c := (t + d >> 1)))
		x = y
	print(r)


def h(m):
	return sum([m[0], m[n - 1], sum([abs(m[i] - m[i + 1]) for i in range(n - 1)])])
for q in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	e = h(m)
	k = 0
	if len(m) > 1:
		if m[0] > m[1]:
			k += m[0] - m[1]
		for i in range(1, n - 1):
			if m[i] > m[i - 1] and m[i] > m[i + 1]:
				k += m[i] - max(m[i - 1], m[i + 1])
		if m[n - 1] > m[n - 2]:
			k += m[n - 1] - m[n - 2]
	else:
		k += m[0]
	print(e - k)


for i in range(int(input())):
	a = int(input())
	b = [int(X) for X in input().split()]
	k = b
	per = 0
	if a >= 2:
		per += b[0] + b[a - 1]
	else:
		per += b[0]
	for z in range(1, a):
		per += abs(k[z] - k[z - 1])
	for j in range(1, a - 1):
		if b[j] > b[j - 1] and b[j] > b[j + 1]:
			per -= b[j] - max(b[j - 1], b[j + 1])
	if len(b) >= 2:
		if b[a - 1] > b[a - 2]:
			per -= b[a - 1] - b[a - 2]
		if b[0] > b[1]:
			per -= b[0] - b[1]
	print(per)


import sys

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	a = [0] + list(map(int, input().split())) + [0]
	cost = 0
	for i in range(1, n + 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			cost += a[i] - max(a[i - 1], a[i + 1])
			a[i] = max(a[i - 1], a[i + 1])
	heights = 0
	for i in range(1, n + 1):
		heights += max(0, a[i] - a[i - 1])
		heights += max(0, a[i] - a[i + 1])
	print(heights + cost)


for t in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	A = [0] + A + [0]
	s = 0
	s += A[1]
	for i in range(1, len(A) - 1):
		s += abs(A[i + 1] - A[i])
		if A[i] > A[i - 1] and A[i] > A[i + 1]:
			m = max(A[i - 1], A[i + 1])
			s -= 2 * (A[i] - m)
			s += A[i] - m
			A[i] = m
	print(s)


T = int(input())
while T > 0:
	n = int(input())
	list1 = [int(x) for x in input().split()]
	if n == 1:
		print(list1[0])
	else:
		op = 0
		for i in range(n):
			if i == 0:
				if list1[1] < list1[0]:
					op += list1[0] - list1[1]
					list1[0] = list1[1]
			elif i == n - 1:
				if list1[n - 2] < list1[n - 1]:
					op += list1[n - 1] - list1[n - 2]
					list1[n - 1] = list1[n - 2]
			elif list1[i] > list1[i - 1] and list1[i] > list1[i + 1]:
				op += list1[i] - max(list1[i - 1], list1[i + 1])
				list1[i] = max(list1[i - 1], list1[i + 1])
		op += list1[0] + list1[n - 1]
		for i in range(0, n - 1):
			op += abs(list1[i] - list1[i + 1])
		print(op)
	T -= 1


import os
import sys
from io import BytesIO, IOBase

def chk(a, b):
	for x in range(len(a)):
		for y in range(len(a[0])):
			if b[x][y] != '.' and b[x][y] != a[x][y]:
				return False
	return True

def main():
	for _ in range(int(input())):
		n = int(input())
		ans = 0
		nums = list(map(int, input().split(' ')))
		if n == 1:
			print(nums[0])
			continue
		here = min(nums)
		for x in range(len(nums)):
			if x == 0:
				if x + 1 < len(nums) and nums[x] > nums[x + 1]:
					prev = nums[x]
					nums[x] = nums[x + 1]
					ans += prev - nums[x]
			elif x == n - 1:
				if x - 1 >= 0 and nums[x] > nums[x - 1]:
					prev = nums[x]
					nums[x] = nums[x - 1]
					ans += prev - nums[x]
			elif nums[x] > nums[x - 1] and nums[x] > nums[x + 1]:
				prev = nums[x]
				nums[x] = max(nums[x + 1], nums[x - 1])
				ans += prev - nums[x]
		ans += nums[0] + nums[-1]
		for x in range(1, len(nums)):
			ans += abs(nums[x] - nums[x - 1])
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	loc = [False for i in range(n)]
	if n == 1:
		print(arr[0])
	else:
		ans = 0
		mx = arr[0]
		for i in range(1, n):
			mx += abs(arr[i] - arr[i - 1])
		mx += arr[-1]
		if n > 1 and arr[0] > arr[1]:
			ans += abs(arr[0] - arr[1])
		for i in range(1, n - 1):
			if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
				ans += arr[i] - max(arr[i - 1], arr[i + 1])
				loc[i] = True
		if n > 1 and arr[-1] > arr[-2]:
			ans += abs(arr[-1] - arr[-2])
		print(mx - ans)


import sys

def ints():
	return list(map(int, sys.stdin.readline().strip().split()))
tc = int(input())
while tc:
	tc -= 1
	n = int(input())
	ls = ints()
	ls = [0] + ls + [0]
	(ans, gap) = (0, 0)
	for i in range(1, n + 1):
		if ls[i] > ls[i - 1] and ls[i] > ls[i + 1]:
			ans += ls[i] - max(ls[i - 1], ls[i + 1])
		gap += abs(ls[i] - ls[i - 1])
	gap += ls[-2]
	print(gap - ans)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l = [0]
	l.extend(l1)
	l.append(0)
	k = 0
	for i in range(1, n + 1):
		if l[i] > l[i - 1] and l[i] > l[i + 1]:
			if l[i - 1] > l[i + 1]:
				k += l[i] - l[i - 1]
				l[i] = l[i - 1]
			else:
				k += l[i] - l[i + 1]
				l[i] = l[i + 1]
	for i in range(1, n + 2):
		k += abs(l[i] - l[i - 1])
	print(k)


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
T = int(input())
for _ in range(T):
	N = int(input())
	A = [0] + list(map(int, input().split())) + [0]
	ans = 0
	for (a1, a2, a3) in zip(A, A[1:], A[2:]):
		if a1 < a2 > a3:
			ma = a1 if a1 > a3 else a3
			ans -= a2 - ma
		if a1 < a2:
			ans += a2 - a1
		if a2 > a3:
			ans += a2 - a3
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a = [0] + a + [0]
	ans = 0
	for i in range(1, n + 1):
		diff = a[i] - max(a[i - 1], a[i + 1])
		if diff > 0:
			ans += diff
			a[i] = a[i] - diff
	for i in range(0, len(a) - 1):
		ans += abs(a[i] - a[i + 1])
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	u = l[0] + l[-1]
	for i in range(n - 1):
		u = u + abs(l[i + 1] - l[i])
	l.insert(0, 0)
	l.append(0)
	for j in range(1, len(l) - 1):
		if l[j] > l[j - 1] and l[j] > l[j + 1]:
			x = min(l[j] - l[j - 1], l[j] - l[j + 1])
			u = u - x
	print(u)


import sys
MOD = 1000000007

def inp():
	return sys.stdin.readline().strip()

def ii():
	return int(inp())

def iis():
	return [int(i) for i in inp().split()]

def solve():
	n = ii()
	a = [0] + iis() + [0]
	min_ugliness = 0
	for i in range(1, n + 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			biggest_neighbour = max(a[i - 1], a[i + 1])
			min_ugliness += a[i] - biggest_neighbour
			a[i] = biggest_neighbour
		if i < n:
			min_ugliness += abs(a[i] - a[i - 1])
	min_ugliness += abs(a[n] - a[n - 1]) + a[n]
	return min_ugliness
t = ii()
for _ in range(t):
	print(solve())


t = int(input())
for _ in range(t):
	n = int(input())
	hist = input().split()
	hist = [int(num) for num in hist if num != ' ']
	hist = [0] + hist + [0, 0]
	(ugliness, i) = (0, 1)
	while i < n + 2:
		if hist[i] > hist[i - 1] and hist[i] > hist[i + 1]:
			ugliness += abs(hist[i - 1] - hist[i + 1]) + min(hist[i] - hist[i + 1], hist[i] - hist[i - 1])
			i += 1
		else:
			ugliness += abs(hist[i] - hist[i - 1])
		i += 1
	print(ugliness)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	u = a[0] + a[-1]
	for i in range(1, len(a)):
		u += abs(a[i] - a[i - 1])
	if len(a) < 2:
		print(u - a[0])
	else:
		if a[0] > a[1]:
			u -= a[0] - a[1]
			a[0] = a[1]
		if a[-1] > a[-2]:
			u -= a[-1] - a[-2]
			a[-1] = a[-2]
		for i in range(1, len(a) - 1):
			m = max(a[i - 1], a[i + 1])
			if a[i] > m:
				u -= a[i] - m
				a[i] = m
		print(u)


for _ in range(int(input())):
	n = int(input())
	temp = 0
	arr = list(map(int, input().strip().split()))
	arr = [0] + arr
	s = sum(arr)
	arr.append(0)
	for i in range(1, n + 1):
		if arr[i] > arr[i + 1] and arr[i] > arr[i - 1]:
			arr[i] = max(arr[i + 1], arr[i - 1])
	cout = 0
	for i in range(len(arr) - 1):
		cout += abs(arr[i] - arr[i + 1])
	print(cout + s - sum(arr))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = a[0] + a[n - 1]
	if n == 1:
		print(a[0])
	else:
		for j in range(n - 1):
			s += abs(a[j] - a[j + 1])
		for i in range(n):
			if i == 0:
				if a[0] > a[1]:
					s -= a[0] - a[1]
			elif i == n - 1:
				if a[n - 2] < a[n - 1]:
					s -= a[n - 1] - a[n - 2]
			elif a[i] > a[i - 1] and a[i] > a[i + 1]:
				s -= a[i] - max(a[i - 1], a[i + 1])
		print(s)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	n += 2
	A = [0] + A + [0]
	tot = 0
	for i in range(1, n):
		tot += abs(A[i] - A[i - 1])
	for i in range(1, n - 1):
		if A[i - 1] < A[i] > A[i + 1]:
			tmp = A[i] - max(A[i - 1], A[i + 1])
			A[i] = max(A[i - 1], A[i + 1])
			tot -= tmp
	print(tot)


def findAns(arr):
	arr = [0] + arr + [0]
	res = 0
	ans = [False] * len(arr)
	for i in range(1, len(arr) - 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			res += arr[i] - max(arr[i - 1], arr[i + 1])
			res += max(arr[i - 1], arr[i + 1]) - min(arr[i - 1], arr[i + 1])
			ans[i] = True
			ans[i + 1] = True
	for j in range(1, len(arr)):
		if ans[j] == False:
			res += abs(arr[j] - arr[j - 1])
	return res
T = int(input())
for i in range(T):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	print(findAns(arr))


m = eval(input())
for t in range(m):
	n = eval(input())
	a = list(map(int, input().split()))
	k = 0
	a = [0] + a + [0]
	for i in range(0, n + 1):
		k += abs(a[i] - a[i + 1])
	for i in range(1, n + 1):
		if a[i - 1] < a[i] and a[i + 1] < a[i]:
			k -= a[i] - max(a[i + 1], a[i - 1])
	print(k)


def solve(A, n):
	li = [0] + A[:] + [0]
	count = 0
	for i in range(1, n + 1):
		a = max(0, li[i] - li[i - 1])
		b = max(0, li[i] - li[i + 1])
		count += a + b - min(a, b)
	return count
for case in range(int(input())):
	n = int(input())
	Arr = list(map(int, input().split()))
	ans = solve(Arr, n)
	print(ans)


t = int(input())
for test in range(t):
	n = int(input())
	inp = list(map(int, input().split()))
	uglyness = 0
	if n == 1:
		print(inp[0])
		continue
	if n == 2:
		uglyness += abs(inp[0] - inp[1])
		uglyness += 2 * min(inp[0], inp[1])
		print(uglyness)
		continue
	if inp[0] > inp[1]:
		uglyness += inp[0] - inp[1]
		inp[0] = inp[1]
	if inp[n - 1] > inp[n - 2]:
		uglyness += inp[n - 1] - inp[n - 2]
		inp[n - 1] = inp[n - 2]
	for i in range(1, n - 1):
		if inp[i] > inp[i - 1] and inp[i] > inp[i + 1]:
			maxNeighbor = max(inp[i - 1], inp[i + 1])
			uglyness += inp[i] - maxNeighbor
			inp[i] = maxNeighbor
	uglyness += inp[0]
	uglyness += inp[n - 1]
	for i in range(1, n):
		uglyness += abs(inp[i] - inp[i - 1])
	print(uglyness)


import math
import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	s = [0] + [int(_) for _ in input().split()] + [0]
	ans = 0
	for i in range(1, n + 1):
		if s[i - 1] < s[i] > s[i + 1]:
			d = s[i] - max(s[i - 1], s[i + 1])
			s[i] -= d
			ans += d
	for i in range(n + 2):
		ans += abs(s[i] - s[i - 1])
	print(ans)
tt = int(input())
for test in range(tt):
	solve()


import sys

def ugly(hist):
	diffs = [abs(i - j) for (i, j) in zip([0] + hist, hist + [0])]
	return sum(diffs)

def solve(hist):
	orig = ugly(hist)
	actions = 0
	something = [max(0, min(cur - next, cur - prev)) for (prev, cur, next) in zip([0] + hist, hist, hist[1:] + [0])]
	return orig - sum(something)

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		hist = list(map(int, input().split()))
		print(solve(hist))
	pass
sys.exit(main())


def ugliness(a, n):
	badsoorat = 0
	for i in range(n):
		if i == 0:
			badsoorat += a[i]
		elif i == n - 1:
			badsoorat += abs(a[i] - a[i - 1])
			badsoorat += a[i]
		else:
			badsoorat += abs(a[i] - a[i - 1])
	return badsoorat

def main(a, n):
	score = ugliness(a, n)
	if n == 1:
		print(a[0])
		return ''
	for i in range(n):
		if i == 0:
			if a[i] > a[i + 1]:
				score -= abs(a[i] - a[i + 1])
		elif i == n - 1:
			if a[i] > a[i - 1]:
				score -= abs(a[i] - a[i - 1])
		elif a[i - 1] < a[i] > a[i + 1]:
			score -= abs(a[i] - max(a[i - 1], a[i + 1]))
	print(score)
	return ''
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	main(a, n)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if i > 0:
			l = a[i - 1]
		else:
			l = 0
		if i + 1 < n:
			r = a[i + 1]
		else:
			r = 0
		v = max(l, r)
		if v < a[i]:
			c += a[i] - v
			a[i] = v
	p = 0
	for i in range(n):
		c += abs(a[i] - p)
		p = a[i]
	c += abs(p)
	print(c)
for i in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	m = int(input())
	arr = list(map(int, input().strip().split()))[:m]
	brr = [0]
	for j in arr:
		brr.append(j)
	brr.append(0)
	crr = [0]
	for j in range(1, m + 1):
		if brr[j] > brr[j - 1] and brr[j] > brr[j + 1]:
			crr.append(max(brr[j - 1], brr[j + 1]))
		else:
			crr.append(brr[j])
	crr.append(0)
	summ = crr[1]
	for j in range(2, m + 1):
		summ += abs(crr[j] - crr[j - 1])
	summ += crr[-2]
	for j in range(1, m + 1):
		summ += brr[j] - crr[j]
	print(summ)


def minimize_ugliness(arr, length):
	ugliness = 0
	for i in range(length):
		while arr[i + 1] > arr[i] and arr[i + 1] > arr[i + 2]:
			temp = arr[i + 1]
			arr[i + 1] = max(arr[i], arr[i + 2])
			ugliness += temp - arr[i + 1]
	for i in range(length + 1):
		ugliness += abs(arr[i + 1] - arr[i])
	return ugliness
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	a.append(0)
	a.insert(0, 0)
	print(minimize_ugliness(a, n))


inp = int(input())
for _ in range(inp):
	n = int(input())
	a = list(map(int, input().split(' ')))
	a = [0] + a[:] + [0]
	origugly = 0
	for i in range(1, len(a)):
		origugly += abs(a[i] - a[i - 1])
	for i in range(1, len(a) - 1):
		if a[i] > a[i + 1] and a[i] > a[i - 1]:
			maxugly = max(a[i + 1], a[i - 1])
			origugly -= a[i] - maxugly
			a[i] = maxugly
	print(origugly)


test = int(input())
for t in range(test):
	total = 0
	n = int(input())
	arr = [0]
	arr += list(map(int, input().split()))
	arr += [0]
	for i in range(1, n + 1):
		total += abs(arr[i] - arr[i - 1])
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			total -= arr[i] - max(arr[i - 1], arr[i + 1])
	total += arr[n]
	print(total)


for _ in range(int(input())):
	n = int(input())
	l = [0] + list(map(int, input().split())) + [0]
	res = 0
	for i in range(1, n + 1):
		if l[i] > l[i - 1] and l[i] > l[i + 1]:
			res += l[i] - max(l[i + 1], l[i - 1])
			l[i] = max(l[i + 1], l[i - 1])
		res += abs(l[i] - l[i - 1])
	print(res + l[-2])


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(l[0])
		continue
	ugly = l[0] + l[-1]
	i = 1
	while i < n:
		ugly += abs(l[i] - l[i - 1])
		i += 1
	if n == 2:
		print(ugly - abs(l[0] - l[1]))
		continue
	ans = 0
	if l[1] < l[0]:
		ans += l[0] - l[1]
	if l[-1] > l[-2]:
		ans += l[-1] - l[-2]
	i = 1
	while i < n - 1:
		if l[i - 1] < l[i] and l[i + 1] < l[i]:
			ans += l[i] - max(l[i - 1], l[i + 1])
		i += 1
	print(ugly - ans)


PI = 3.141592653589793
INF = float('inf')
MOD = 1000000007

def add(x, y):
	return (x + y) % MOD

def sub(x, y):
	return (x - y + MOD) % MOD

def mul(x, y):
	return x * y % MOD

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def lcm(x, y):
	return x * y // gcd(x, y)

def power(x, y):
	res = 1
	x %= MOD
	while y != 0:
		if y & 1:
			res = mul(res, x)
		y >>= 1
		x = mul(x, x)
	return res

def mod_inv(n):
	return power(n, MOD - 2)

def prob(p, q):
	return mul(p, power(q, MOD - 2))

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

def li():
	return [int(i) for i in input().split()]

def ls():
	return [i for i in input().split()]
for t in range(ii()):
	t += 1
	n = ii()
	a = li()
	a.insert(0, 0)
	a.append(0)
	total = 0
	store = []
	for i in range(1, n + 1):
		store.append([a[i], i])
	store.sort()
	store.reverse()
	for j in store:
		i = j[1]
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			mx = max(a[i - 1], a[i + 1])
			total += a[i] - mx
			a[i] = mx
	for i in range(1, n + 2):
		total += abs(a[i] - a[i - 1])
	print(total)


from __future__ import division, print_function
import bisect
import math
import heapq
import itertools
import sys
from collections import deque
from atexit import register
from collections import Counter
from functools import reduce
if sys.version_info[0] < 3:
	from io import BytesIO as stream
else:
	from io import StringIO as stream
if sys.version_info[0] < 3:

	class dict(dict):

		def items(self):
			return dict.iteritems(self)

		def keys(self):
			return dict.iterkeys(self)

		def values(self):
			return dict.itervalues(self)
	input = raw_input
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip

def sync_with_stdio(sync=True):
	global input, flush
	if sync:
		flush = sys.stdout.flush
	else:
		sys.stdin = stream(sys.stdin.read())
		input = lambda : sys.stdin.readline().rstrip('\r\n')
		sys.stdout = stream()
		register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.insert(0, 0)
	val = 0
	c = 0
	a.append(0)
	if n == 1:
		print(a[1])
		continue
	else:
		for i in range(1, n + 1):
			if a[i - 1] < a[i] > a[i + 1]:
				val += a[i] - max(a[i - 1], a[i + 1])
				a[i] = max(a[i - 1], a[i + 1])
		for i in range(n + 1):
			val += abs(a[i] - a[i + 1])
	print(val)


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


t = int(input())
for test in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(arr[0])
	elif n == 2:
		print(arr[0] + arr[1])
	else:
		ans = 0
		for i in range(n):
			if i == 0 and arr[i + 1] < arr[i]:
				ans += arr[i] - arr[i + 1]
				arr[i] = arr[i + 1]
			elif i == n - 1 and arr[i - 1] < arr[i]:
				ans += arr[i] - arr[i - 1]
				arr[i] = arr[i - 1]
			elif arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
				ans += arr[i] - max(arr[i - 1], arr[i + 1])
				arr[i] = max(arr[i - 1], arr[i + 1])
		ans += arr[0] + arr[-1]
		for i in range(1, n):
			ans += abs(arr[i] - arr[i - 1])
		print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def connected_components(n, graph):
	(components, visited) = ([], [False] * n)

	def dfs(start):
		(component, stack) = ([], [start])
		while stack:
			start = stack[-1]
			if visited[start]:
				stack.pop()
				continue
			else:
				visited[start] = True
				component.append(start)
			for i in graph[start]:
				if not visited[i]:
					stack.append(i)
		return component
	for i in range(n):
		if not visited[i]:
			components.append(dfs(i))
	return components
for _ in range(int(input()) if True else 1):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	stack = []
	a = [0] + a + [0]
	for i in range(1, n + 1):
		if a[i] > max(a[i - 1], a[i + 1]):
			ans += a[i] - max(a[i - 1], a[i + 1])
			a[i] = max(a[i - 1], a[i + 1])
	print(ans + sum((abs(a[i] - a[i - 1]) for i in range(1, n + 2))))


def fealdad_a_medias(lista):
	result = 0
	for i in range(len(lista) - 1):
		result += abs(lista[i] - lista[i + 1])
	return lista[0] + lista[-1] + result
for i in range(int(input())):
	n = int(input())
	lista = list(map(int, input().split()))
	contador = fealdad_a_medias(lista)
	lista_aumentada = [0] + lista + [0]
	h = 0
	for k in range(1, n + 1):
		if lista_aumentada[k] > lista_aumentada[k - 1] and lista_aumentada[k - 1] >= lista_aumentada[k + 1]:
			h += lista_aumentada[k] - lista_aumentada[k - 1]
		elif lista_aumentada[k] > lista_aumentada[k + 1] and lista_aumentada[k + 1] >= lista_aumentada[k - 1]:
			h += lista_aumentada[k] - lista_aumentada[k + 1]
	print(fealdad_a_medias(lista) - h)


import sys, os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n > 2:
		moves = 0
		for i in range(1, n - 1):
			if a[i] > a[i - 1] and a[i] > a[i + 1]:
				moves += a[i] - max(a[i - 1], a[i + 1])
				a[i] = max(a[i - 1], a[i + 1])
		if a[0] > a[1]:
			moves += a[0] - a[1]
			a[0] = a[1]
		if a[-1] > a[-2]:
			moves += a[-1] - a[-2]
			a[-1] = a[-2]
		s = a[0] + a[-1]
		for i in range(1, n):
			s += abs(a[i] - a[i - 1])
		ans = s + moves
		print(ans)
	elif n == 2:
		s = 2 * min(a)
		s += max(a) - min(a)
		print(s)
	else:
		print(a[0])


def solve(l, n):
	if n == 1:
		print(l[0])
	else:
		ans = 0
		for i in range(n):
			if i == 0:
				ans += l[i]
			else:
				ans += abs(l[i] - l[i - 1])
		ans += l[-1]
		for i in range(n):
			if i == 0:
				ans -= max(0, l[i] - l[i + 1])
			elif i > 0 and i < n - 1:
				ans -= max(0, l[i] - max(l[i - 1], l[i + 1]))
			else:
				ans -= max(0, l[i] - l[i - 1])
		print(ans)
for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	solve(l, n)


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	A = [0] + A + [0]
	res = 0
	for i in range(1, n + 1):
		if A[i - 1] < A[i] and A[i] > A[i + 1]:
			pre = A[i]
			A[i] = max(A[i - 1], A[i + 1])
			res += pre - A[i]
	for i in range(1, n + 2):
		d = A[i] - A[i - 1]
		res += abs(d)
	print(res)


t = int(input())
while t:
	sdd = int(input())
	sdfdgdg = list(map(int, input().split()))
	if sdd == 1:
		print(sdfdgdg[0])
	else:
		x = 0
		if sdfdgdg[0] > sdfdgdg[1]:
			x += sdfdgdg[0] - sdfdgdg[1]
			sdfdgdg[0] = sdfdgdg[1]
		if sdfdgdg[-1] > sdfdgdg[-2]:
			x += abs(sdfdgdg[-1] - sdfdgdg[-2])
			sdfdgdg[-1] = sdfdgdg[-2]
		for i in range(1, sdd - 1):
			if sdfdgdg[i] > sdfdgdg[i - 1] and sdfdgdg[i] > sdfdgdg[i + 1]:
				x += sdfdgdg[i] - max(sdfdgdg[i - 1], sdfdgdg[i + 1])
				sdfdgdg[i] = max(sdfdgdg[i - 1], sdfdgdg[i + 1])
		x += sdfdgdg[0]
		x += sdfdgdg[-1]
		for i in range(1, sdd):
			x += abs(sdfdgdg[i] - sdfdgdg[i - 1])
		print(x)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	res = 0
	a = map(int, input().split())
	p = 0
	pp = 0
	ugly = 0
	for k in a:
		if k > p:
			ugly += k - p
			pp = p
		else:
			down = max(0, min(p - k, p - pp))
			ugly += p - k - down
			pp = p - down
		p = k
	down = max(0, min(p, p - pp))
	ugly += p - down
	print(ugly)


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


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = [int(ai) for ai in input().split()]
		initial = 0
		prev = 0
		for ai in a:
			initial += abs(ai - prev)
			prev = ai
		initial += prev
		sol = 0
		for i in range(n):
			p = a[i - 1] if i else 0
			l = a[i + 1] if i + 1 != n else 0
			if p < a[i] > l:
				sol += a[i] - max(p, l)
				a[i] = max(p, l)
		print(initial - sol)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os, sys
from io import BytesIO, IOBase
from collections import deque, Counter, defaultdict as dft
from heapq import heappop, heappush
from math import log, sqrt, factorial, cos, tan, sin, radians, log2, ceil, floor
from bisect import bisect, bisect_left, bisect_right
from decimal import *
import sys, threading
from itertools import permutations, combinations
from copy import deepcopy
input = sys.stdin.readline
ii = lambda : int(input())
si = lambda : input().rstrip()
mp = lambda : map(int, input().split())
ms = lambda : map(str, input().strip().split(' '))
ml = lambda : list(mp())
mf = lambda : map(float, input().split())
alphs = 'abcdefghijklmnopqrstuvwxyz'

def solve():
	n = ii()
	arr = ml()
	res = 0
	arr = [0] + arr + [0]
	for i in range(1, n + 1):
		mx = max(arr[i - 1], arr[i + 1])
		if arr[i] > mx:
			res += arr[i] - mx
			arr[i] = mx
		res += abs(arr[i] - arr[i - 1])
	print(res + arr[-2])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
tc = 1
tc = ii()
for i in range(tc):
	solve()


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	n = int(input())
	A = [0] + list(map(int, input().split())) + [0]
	if n == 1:
		print(A[1])
		continue
	ANS = 0
	for i in range(1, len(A)):
		if A[i] > A[i - 1] and A[i] > A[i + 1]:
			MAX = max(A[i - 1], A[i + 1])
			ANS += A[i] - MAX
			A[i] = MAX
		ANS += abs(A[i] - A[i - 1])
	print(ANS)


def Histogram(n, arr):
	res = [0] * (n + 2)
	for i in range(1, n + 1):
		res[i] = arr[i - 1]
	ans = 0
	for i in range(1, n + 1):
		s = min(res[i], max(res[i - 1], res[i + 1]))
		ans += res[i] - s + abs(s - res[i - 1])
		res[i] = s
	return ans + res[n]
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(Histogram(n, arr))


import sys
import math
import heapq

def input():
	return sys.stdin.readline().strip('\n')

def I():
	return input()

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

def MI():
	return map(int, input().split())

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

def isPerfectSquare(x):
	return int(math.sqrt(x)) ** 2 == x
for _ in range(II()):
	n = II()
	a = LI()
	b = [0]
	if n == 1:
		print(a[0])
	else:
		for i in a:
			b.append(i)
		b.append(0)
		ans = 0
		minugly = 0
		for i in range(1, n + 1):
			if b[i - 1] < b[i] > b[i + 1]:
				l = abs(b[i] - b[i - 1])
				m = abs(b[i + 1] - b[i])
				mini = min(l, m)
				ans += mini
				if l == mini:
					b[i] = b[i - 1]
				else:
					b[i] = b[i + 1]
		for i in range(1, n + 2):
			minugly += abs(b[i] - b[i - 1])
		print(minugly + ans)


from sys import stdin

def main():
	t = int(stdin.readline())
	for _ in range(t):
		solve()

def solve():
	n = int(stdin.readline())
	numbers = (int(num) for num in stdin.readline().split())
	previous = 0
	pre_previous = 0
	ugliness = 0
	for current in numbers:
		diff = abs(current - previous)
		ugliness += diff
		cut = 0
		if pre_previous < previous > current:
			cut = previous - max(pre_previous, current)
		ugliness -= cut
		pre_previous = previous
		previous = current
	ugliness += previous
	if pre_previous < previous:
		ugliness -= previous - pre_previous
	print(ugliness)
main()


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

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


import sys
input = sys.stdin.readline
sys.setrecursionlimit(3 * 10 ** 5)

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	n = inp()
	a = lis()
	if n == 1:
		print(a[0])
		continue
	z = 0
	for i in range(n):
		if i == 0:
			if a[i] > a[i + 1]:
				z += a[i] - a[i + 1]
				a[i] = a[i + 1]
		elif i == n - 1:
			if a[i] > a[-2]:
				z += a[i] - a[-2]
				a[i] = a[-2]
		else:
			c = max(a[i - 1], a[i + 1])
			if a[i] > c:
				z += a[i] - c
				a[i] = c
	tot = 0
	for i in range(n):
		if i == 0 or i == n - 1:
			tot += a[i]
		if i != n - 1:
			tot += abs(a[i] - a[i + 1])
	print(tot + z)


import heapq, math
from collections import defaultdict, deque
from os import getcwd
import sys, os.path
if os.path.exists('C:/Users/Dhanush/Desktop/cp/input.txt'):
	sys.stdout = open('C:/Users/Dhanush/Desktop/cp/output.txt', 'w')
	sys.stdin = open('C:/Users/Dhanush/Desktop/cp/input.txt', 'r')
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(l[0])
	elif n == 2:
		mini = min(l[0], l[1])
		maxi = max(l[0], l[1])
		print(2 * mini + (maxi - mini))
	else:
		ans = 0
		for i in range(1, n - 1):
			if l[i] > l[i - 1] and l[i] > l[i + 1]:
				maxi = max(l[i - 1], l[i + 1])
				ans += l[i] - maxi
				l[i] = maxi
		if l[0] > l[1]:
			ans += l[0] - l[1]
			l[0] = l[1]
		if l[-1] > l[-2]:
			ans += l[-1] - l[-2]
			l[-1] = l[-2]
		ans += l[0]
		for i in range(1, n):
			ans += abs(l[i] - l[i - 1])
		ans += l[-1]
		print(ans)


def solution(n, a):
	(prev, cur) = (0, a[0])
	a.append(0)
	cnt = 0
	for i in range(1, n + 1):
		prev = cur
		cur = a[i] - a[i - 1]
		if prev > 0 and cur < 0:
			cnt += min(abs(prev), abs(cur))
			a[i - 1] -= min(abs(prev), abs(cur))
	outline = a[0]
	for i in range(1, n + 1):
		outline += abs(a[i] - a[i - 1])
	return cnt + outline
tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	print(solution(n, a))


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
for _ in range(stdint()):
	n = stdint()
	arr = stdarr()
	cop = arr.copy()
	cop = [0] + cop + [0]
	init = 0
	extra = Counter()
	for i in range(1, len(cop)):
		init += abs(cop[i] - cop[i - 1])
	res = init
	moves = 0
	for i in range(1, len(cop) - 1):
		prev = cop[i - 1]
		next = cop[i + 1]
		curr = cop[i]
		if prev < curr and next < curr:
			diff = curr - max(prev, next)
			res -= diff * 2
			moves += diff
	print(res + moves)


import sys, math

def solve(arr):
	arr = [0] + arr + [0]
	res = 0
	for i in range(0, len(arr) - 2):
		(a, b, c) = arr[i:i + 3]
		m = max(a, c)
		if b > m:
			arr[i + 1] = m
			res += b - m
	s = 0
	prev = 0
	for v in arr:
		s += abs(prev - v)
		prev = v
	return s + res
for _ in '_' * int(input()):
	input()
	print(solve([*map(int, input().split())]))


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	extra = 0
	if n == 1:
		print(lst[0])
		continue
	for i in range(n):
		if i == 0:
			if lst[i] > lst[i + 1]:
				extra += abs(lst[i] - lst[i + 1])
				lst[i] = lst[i + 1]
		elif i == n - 1:
			if lst[i] > lst[i - 1]:
				extra += abs(lst[i] - lst[i - 1])
				lst[i] = lst[i - 1]
		elif lst[i] > lst[i - 1] and lst[i] > lst[i + 1]:
			val1 = abs(lst[i] - lst[i + 1])
			val2 = abs(lst[i] - lst[i - 1])
			extra += min(val1, val2)
			lst[i] = max(lst[i - 1], lst[i + 1])
	for i in range(n):
		if i == 0:
			extra += lst[i]
		else:
			extra += abs(lst[i] - lst[i - 1])
	extra += lst[-1]
	print(extra)


from collections import *
import bisect
import math
inf = 10 ** 18
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = a.copy()
	if n == 1:
		print(a[0])
		continue
	for i in range(n):
		if i == 0:
			a[i] = min(a[i], a[i + 1])
		elif i == n - 1:
			a[i] = min(a[i], a[i - 1])
		else:
			a[i] = min(max(a[i - 1], a[i + 1]), a[i])
	cost = 0
	for i in range(n):
		cost += c[i] - a[i]
	for i in range(n):
		if i == 0:
			cost += a[i]
		elif i == n - 1:
			cost += abs(a[i] - a[i - 1])
			cost += a[i]
		else:
			cost += abs(a[i] - a[i - 1])
	print(cost)


T = int(input())
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	cost = 0
	length = 0
	if n == 1:
		print(arr[0])
	else:
		for i in range(n):
			if i == 0:
				if arr[i] > arr[i + 1]:
					cost += arr[i] - arr[i + 1]
					arr[i] = arr[i + 1]
				length += arr[i]
			elif i == n - 1:
				if arr[i] > arr[i - 1]:
					cost += arr[i] - arr[i - 1]
					arr[i] = arr[i - 1]
				length += arr[i]
			else:
				if arr[i - 1] < arr[i] > arr[i + 1]:
					cost += arr[i] - max(arr[i - 1], arr[i + 1])
					arr[i] -= arr[i] - max(arr[i - 1], arr[i + 1])
				if arr[i] > arr[i - 1]:
					length += arr[i] - arr[i - 1]
				if arr[i] > arr[i + 1]:
					length += arr[i] - arr[i + 1]
		print(length + cost)


from __future__ import print_function
from collections import *
from sys import stdin
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(t,) = gil()
for _ in range(t):
	(n,) = gil()
	a = [0] + gil() + [0]
	ans = 0
	for i in range(1, n + 2):
		ans += abs(a[i] - a[i - 1])
	for i in range(1, n + 1):
		if a[i - 1] < a[i] > a[i + 1]:
			ans -= a[i] - max(a[i - 1], a[i + 1])
	print(ans)


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

def si():
	return input()

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

def msi():
	return map(str, input().split())

def li():
	return list(mi())
t = ii()
for _ in range(t):
	n = ii()
	a = li()
	if n == 1:
		print(a[0])
	else:
		ans = 0
		for i in range(n):
			if i == 0:
				if a[i] > a[i + 1]:
					ans += a[i] - a[i + 1]
					a[i] = a[i + 1]
			elif i == n - 1:
				if a[i] > a[i - 1]:
					ans += a[i] - a[i - 1]
					a[i] = a[i - 1]
			elif a[i] > a[i + 1] and a[i] > a[i - 1]:
				if a[i - 1] >= a[i + 1]:
					ans += a[i] - a[i - 1]
					a[i] = a[i - 1]
				else:
					ans += a[i] - a[i + 1]
					a[i] = a[i + 1]
		for i in range(n - 1):
			ans += abs(a[i + 1] - a[i])
		ans += a[0] + a[-1]
		print(ans)


for i in range(int(input())):
	m = int(input())
	l = list(map(int, input().split()))
	l.append(0)
	l.insert(0, 0)
	c = 0
	for i in range(1, m + 2):
		c += abs(l[i] - l[i - 1])
	for i in range(1, m + 1):
		if l[i] > l[i - 1] and l[i] > l[i + 1]:
			c -= abs(l[i] - max(l[i - 1], l[i + 1]))
			l[i] = max(l[i - 1], l[i + 1])
	print(c)


for _ in range(int(input())):
	n = int(input())
	(y, z) = (0, 0)
	u = 0
	for a in map(int, input().split() + [0, 0]):
		(x, y, z) = (y, z, a)
		if x < y and y > z:
			d = y - max(x, z)
			u += d
			y -= d
		u += abs(x - y)
	print(u)


import sys
input = sys.stdin.readline
import math
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr = [0] + arr
	arr.append(0)
	ops = 0
	for i in range(1, n + 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			x = arr[i] - max(arr[i - 1], arr[i + 1])
			arr[i] = arr[i] - x
			ops = ops + x
	ans = ops
	for i in range(1, n + 1):
		if arr[i] > arr[i - 1]:
			ans = ans + arr[i] - arr[i - 1]
		if arr[i] > arr[i + 1]:
			ans = ans + arr[i] - arr[i + 1]
	print(ans)


cc = int(input())
for g in range(cc):
	n = int(input())
	l = list(map(int, input().split()))
	ugli = 0
	ugli = ugli + l[0]
	ugli = ugli + l[n - 1]
	for i in range(len(l) - 1):
		ugli += abs(l[i + 1] - l[i])
	total = ugli
	for i in range(1, len(l) - 1):
		if l[i] > l[i + 1] and l[i] > l[i - 1]:
			total -= abs(max(l[i + 1], l[i - 1]) - l[i])
	if n > 1:
		if l[0] > l[1]:
			total -= abs(l[1] - l[0])
		if l[n - 1] > l[n - 2]:
			total -= abs(l[n - 1] - l[n - 2])
	else:
		total = l[0]
	print(total)


cases = int(input())
for _ in range(cases):
	num = int(input())
	arr = [0] + list(map(int, input().split())) + [0]
	ln = num + 2
	sm = 0
	for i in range(1, ln):
		sm += abs(arr[i - 1] - arr[i])
	for i in range(1, ln - 1):
		if arr[i - 1] < arr[i] > arr[i + 1]:
			sm -= arr[i] - max(arr[i - 1], arr[i + 1])
	print(sm)


def get_sum(a, op):
	res = op
	for k in range(1, len(a)):
		res += abs(a[k] - a[k - 1])
	return res
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.insert(0, 0)
	a.append(0)
	mins = 100000000
	ops = 0
	for k in range(n + 1):
		if a[k] > a[k - 1] and a[k] > a[k + 1]:
			raz = a[k] - max(a[k - 1], a[k + 1])
			a[k] = max(a[k - 1], a[k + 1])
			ops += raz
	print(get_sum(a, ops))


def ii():
	return map(int, input().split())

def ti():
	return int(input())

def lis():
	return [int(i) for i in input().split()]

def maxSub(a, size):
	best = a[0]
	su = 0
	(start, stop) = (0, 0)
	for i in range(size):
		if su > 0:
			su += a[i]
		else:
			su = a[i]
			temp = i
		if su >= best:
			best = su
			start = temp
			stop = i
	return (best, start, stop)
mod = 1000000007

def mexp(n, m):
	res = 1
	ans = 1
	b = 2
	while n > 0:
		if n & 1:
			ans *= b % mod
		b = b * b % mod
		n = n >> 1
		ans %= mod
	ans -= 1
	while m > 0:
		if m & 1:
			res *= ans % mod
		ans = ans * ans % mod
		m = m >> 1
		res %= mod
	return res
for i in range(ti()):
	n = ti()
	l = lis()
	u = l[0] + l[-1]
	if n == 1:
		print(l[0])
	else:
		for i in range(1, n):
			u += abs(l[i] - l[i - 1])
		if l[0] > l[1]:
			u -= l[0] - l[1]
			l[0] = l[1]
		for i in range(1, n - 1):
			if l[i] > max(l[i - 1], l[i + 1]):
				u -= l[i] - max(l[i - 1], l[i + 1])
				l[i] = max(l[i - 1], l[i + 1])
		if l[-1] > l[-2]:
			u -= l[-1] - l[-2]
		print(u)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = [0]
	s += list(map(int, input().split())) + [0]
	c = 0
	for i in range(1, n + 1):
		if s[i - 1] <= s[i] >= s[i + 1]:
			x = max(s[i - 1], s[i + 1])
			c += s[i] - x
			s[i] = x
		c += abs(s[i] - s[i - 1])
	print(c + s[-2])


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


t = input()
for i in range(int(t)):
	n = int(input())
	a = [0]
	a = a + list(map(int, input().split()))
	a.append(0)
	ans = 0
	for k in range(1, n + 2):
		ans = ans + abs(a[k] - a[k - 1])
	for k in range(1, n + 1):
		if a[k] > a[k - 1] and a[k] > a[k + 1]:
			ans = ans - (a[k] - max(a[k - 1], a[k + 1]))
	print(ans)


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


import sys
from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
ANS = []
input = stdin.readline

def solve():
	pass
t = int(input())
for i in range(t):
	n = int(input()) + 2
	arr = [0] + list(map(int, input().split())) + [0]
	moves = 0
	for i in range(n - 1):
		moves += abs(arr[i] - arr[i + 1])
	for i in range(1, n - 1):
		sub = arr[i] - max(arr[i - 1], arr[i + 1])
		if sub > 0:
			moves -= sub
	ANS.append(str(moves))
print('\n'.join(ANS))


for _ in range(int(input())):
	n = int(input())
	arr = [int(w) for w in input().split(' ')]
	if n == 1:
		ans = arr[0]
		print(ans)
	else:
		ans = arr[0] + arr[-1]
		for i in range(1, n):
			ans = ans + abs(arr[i] - arr[i - 1])
		res = 0
		for i in range(1, n - 1):
			if arr[i] > arr[i + 1] and arr[i] > arr[i - 1]:
				res = res + arr[i] - max(arr[i + 1], arr[i - 1])
		if arr[0] > arr[1]:
			res = res + arr[0] - arr[1]
		if arr[-1] > arr[-2]:
			res = res + arr[-1] - arr[-2]
		print(ans - res)


for _ in range(int(input())):
	l = [0]
	n = int(input())
	for i in input().split():
		l.append(int(i))
	l.append(0)
	if n == 1:
		print(l[1])
		continue
	ans = 0
	for i in range(1, n + 1):
		if l[i] > l[i - 1] and l[i] > l[i + 1]:
			ans += l[i] - max(l[i - 1], l[i + 1])
			l[i] = max(l[i - 1], l[i + 1])
	for (i, j) in zip(l, l[1:]):
		ans += abs(i - j)
	print(ans)


for _ in range(int(input())):
	input()
	ls = [int(i) for i in input().split()]
	ret = 0
	pre = 0
	for i in ls:
		ret += abs(i - pre)
		pre = i
	ret += pre
	ls = [0] + ls + [0]
	for i in range(1, len(ls) - 1):
		if max(ls[i], ls[i - 1], ls[i + 1]) == ls[i]:
			if ls[i - 1] >= ls[i + 1]:
				ret -= ls[i] - ls[i - 1]
				ls[i] = ls[i - 1]
			else:
				ret -= ls[i] - ls[i + 1]
				ls[i] = ls[i + 1]
	print(ret)


import math
NO = 'NO'
YES = 'YES'
MOD = 1000000007
ALPH = 'abcdefghijklmnopqrstuvwxyz'

def input_int():
	return int(input())

def input_list():
	return input().split(' ')

def input_list_int():
	return list(map(int, input_list()))

def list_int_to_str(a, sep=' '):
	return sep.join((str(x) for x in a))
global_ans = []

def pr(a):
	global_ans.append(a)

def solve():
	n = input_int()
	a = [0] + input_list_int() + [0]
	n += 2
	ans = 0
	for i in range(1, n - 1):
		mx = max(a[i - 1], a[i + 1])
		if a[i] > mx:
			ans += a[i] - mx
			a[i] = mx
	for i in range(1, n):
		ans += abs(a[i] - a[i - 1])
	pr(ans)
query_count = 1
query_count = input_int()
while query_count:
	query_count -= 1
	solve()
for global_ans_line in global_ans:
	print(global_ans_line)


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


from collections import Counter
from sys import stdin, stderr
input = stdin.readline

def dbp(*args, **kwargs):
	print(*args, file=stderr, **kwargs)

def get_int_list():
	return [int(x) for x in input().strip().split()]

def do_thing():
	n = int(input())
	alist = get_int_list()
	ugly = 0
	last = 0
	for (idx, a) in enumerate(alist):
		delta = a - last
		alist[idx] = delta
		ugly += abs(delta)
		last = a
	delta = -last
	alist.append(delta)
	ugly += last
	for (idx, a) in enumerate(alist):
		if idx == 0:
			last = a
			continue
		if last > 0 and a < 0:
			squash = min(last, -a)
			ugly -= squash
		last = a
	return ugly

def multicase():
	maxcc = int(input().strip())
	for cc in range(maxcc):
		print(do_thing())
multicase()


for _ in range(int(input())):
	N = int(input())
	n = list(map(int, input().split()))
	if N == 1:
		print(n[0])
		continue
	rm = 0
	if n[0] > n[1]:
		rm += n[0] - n[1]
		n[0] = n[1]
	if n[-1] > n[-2]:
		rm += n[-1] - n[-2]
		n[-1] = n[-2]
	for i in range(N - 2):
		if n[i + 1] > n[i] and n[i + 1] > n[i + 2]:
			rm += n[i + 1] - max(n[i], n[i + 2])
			n[i + 1] = max(n[i], n[i + 2])
	tot = 0
	for i in range(N - 1):
		upwards = n[i + 1] - n[i]
		if upwards > 0:
			tot += upwards
		downwards = n[i] - n[i + 1]
		if downwards > 0:
			tot += downwards
	tot += n[0]
	tot += n[-1]
	print(tot + rm)


import sys
import math
import random
from queue import PriorityQueue as PQ
from bisect import bisect_left as BSL
from bisect import bisect_right as BSR
from collections import OrderedDict as OD
from itertools import permutations
mod = 1000000007
sys.setrecursionlimit(1000000)

def get_ints():
	return map(int, input().split())

def palindrome(s):
	mid = len(s) // 2
	for i in range(mid):
		if s[i] != s[len(s) - i - 1]:
			return False
	return True

def check(i, n):
	if 0 <= i < n:
		return True
	else:
		return False

def solve(arr, n):
	arr = [0] + arr + [0]
	ans = 0
	for i in range(1, n + 1):
		if arr[i - 1] < arr[i] > arr[i + 1]:
			mi = max(arr[i - 1], arr[i + 1])
			ans += arr[i] - mi
			arr[i] = mi
	for i in range(1, n + 2):
		ans += abs(arr[i] - arr[i - 1])
	print(ans)
t = int(input())
for tt in range(t):
	n = int(input())
	arr = list(get_ints())
	solve(arr, n)


t = int(input())
for i in range(t):
	n = int(input())
	l = input().split()
	for j in range(len(l)):
		l[j] = int(l[j])
	if n <= 2:
		print(sum(l))
	if n > 2:
		c = l[0] + l[n - 1]
		if l[0] > l[1]:
			c -= l[0] - l[1]
		if l[-1] > l[-2]:
			c -= l[-1] - l[-2]
		for j in range(0, n - 1):
			c += abs(l[j] - l[j + 1])
		for j in range(1, n - 1):
			if l[j] > l[j - 1] and l[j] > l[j + 1]:
				c -= l[j] - max(l[j - 1], l[j + 1])
		print(c)


import sys
import math
input = sys.stdin.readline
imp = 'IMPOSSIBLE'
t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	a.append(0)
	res = a[0]
	nove = a[0]
	for i in range(1, n + 1):
		if a[i] > a[i - 1]:
			nove = a[i] - a[i - 1]
			res += nove
		elif a[i] == a[i - 1]:
			nove = 0
		else:
			res = res + max(a[i - 1] - a[i] - nove, 0)
			nove = 0
	print(res)


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


t = int(input())
for p in range(t):
	n = int(input())
	l = list(map(int, input().split(' ')))
	sum = 0
	for i in range(n):
		if i == 0:
			sum += l[i]
		else:
			sum += abs(l[i] - l[i - 1])
	sum += l[n - 1]
	for i in range(1, n - 1):
		if l[i - 1] < l[i] and l[i] > l[i + 1]:
			sum -= abs(max(l[i - 1], l[i + 1]) - l[i])
			l[i] = max(l[i - 1], l[i + 1])
	if n > 1:
		if l[1] < l[0]:
			sum -= abs(l[0] - l[1])
		if l[n - 1] > l[n - 2]:
			sum -= abs(l[n - 1] - l[n - 2])
	else:
		sum = l[0]
	print(sum)


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


t = int(input())
while t:
	n = int(input())
	ops = 0
	levels = [0] + list(map(int, input().split(' '))) + [0]
	for i in range(1, len(levels) - 1):
		if levels[i] > levels[i + 1] and levels[i] > levels[i - 1]:
			nearest = max(levels[i + 1], levels[i - 1])
			ops += levels[i] - nearest
			levels[i] = nearest
	levels = levels[1:-1]
	diffs = [levels[0]] + [abs(levels[i + 1] - levels[i]) for i in range(n - 1)] + [levels[-1]]
	print(sum(diffs) + ops)
	t -= 1


T = int(input())
for t in range(T):
	n = int(input())
	histogram = [int(x) for x in input().split()]
	perimeter = histogram[0] + histogram[n - 1]
	for i in range(1, n):
		perimeter += abs(histogram[i] - histogram[i - 1])
	histogram_new = [0] + histogram + [0]
	for i in range(2, len(histogram_new)):
		if histogram_new[i - 2] <= histogram_new[i - 1] and histogram_new[i - 1] >= histogram_new[i]:
			perimeter -= abs(max(histogram_new[i - 2], histogram_new[i]) - histogram_new[i - 1])
			histogram_new[i - 1] = max(histogram_new[i - 2], histogram_new[i])
	print(perimeter)


from math import sqrt, ceil, floor
import sys
from collections import Counter, deque
from collections import defaultdict as dd

def score(arr):
	ans = 0
	for i in range(len(arr) - 1):
		ans += abs(arr[i + 1] - arr[i])
	return ans + arr[0] + arr[-1] - arr[0] * int(len(arr) == 1)
t = int(input())
for tt in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	if n > 1:
		if arr[0] > arr[1]:
			ans += arr[0] - arr[1]
			arr[0] = arr[1]
		if arr[-1] > arr[-2]:
			ans += arr[-1] - arr[-2]
			arr[-1] = arr[-2]
	for i in range(1, n - 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			ans += arr[i] - max(arr[i - 1], arr[i + 1])
			arr[i] = max(arr[i - 1], arr[i + 1])
	print(score(arr) + ans)


def solve():
	save = 0
	steps = A[0]
	for i in range(N):
		prev = A[i - 1] if i > 0 else 0
		nxt = A[i + 1] if i < N - 1 else 0
		if prev < A[i] > nxt:
			save += min(A[i] - prev, A[i] - nxt)
		steps += abs(A[i] - nxt)
	return steps - save
test_cases = int(input())
for test_case in range(test_cases):
	N = int(input())
	A = list(map(int, input().split()))
	print(solve())


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, sys.stdin.readline().split()))
	ops = 0
	if n == 1:
		print(a[0])
		continue
	if a[0] > a[1]:
		ops += a[0] - a[1]
		a[0] = a[1]
	for i in range(1, len(a) - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			ops += a[i] - max(a[i - 1], a[i + 1])
			a[i] = max(a[i - 1], a[i + 1])
	if a[len(a) - 1] > a[len(a) - 2]:
		ops += a[len(a) - 1] - a[len(a) - 2]
		a[len(a) - 1] = a[len(a) - 2]
	h = a[0] + a[len(a) - 1]
	for i in range(len(a) - 1):
		h += abs(a[i + 1] - a[i])
	print(ops + h)


def hist_sum(A):
	n = len(A)
	S = 0
	for i in range(n - 1):
		S += abs(A[i + 1] - A[i])
	return S

def process(A):
	n = len(A)
	A2 = [0]
	for i in range(n):
		A2.append(A[i])
	A2.append(0)
	d = 0
	for i in range(1, n + 1):
		if A2[i] > max(A2[i - 1], A2[i + 1]):
			delta = A2[i] - max(A2[i - 1], A2[i + 1])
			d += delta
			A2[i] = max(A2[i - 1], A2[i + 1])
	return hist_sum(A2) + d
t = int(input())
for i in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	print(process(A))


for _ in range(int(input())):
	n = int(input())
	daf = list(map(int, input().split()))
	daf = [0] + daf + [0]
	sum_daf = 0
	for i in range(len(daf) - 1):
		sum_daf += abs(daf[i] - daf[i + 1])
	for i in range(n):
		if daf[i + 1] > daf[i] and daf[i + 1] > daf[i + 2]:
			sum_daf -= daf[i + 1] - max(daf[i], daf[i + 2])
	print(sum_daf)


def ugly(n, list):
	list.insert(0, 0)
	list.append(0)
	n += 1
	cost = 0
	count = 0
	for i in range(0, n):
		m = max(list[i - 1], list[i + 1])
		if list[i] > m:
			count += list[i] - m
		if list[i] > list[i - 1]:
			cost += list[i] - list[i - 1]
		if list[i] > list[i + 1]:
			cost += list[i] - list[i + 1]
	return cost - count
for _ in range(int(input())):
	n = int(input())
	print(ugly(n, [int(x) for x in input().split()]))


def sol(a, n):
	a = [0] + a
	s = sum(a)
	a.append(0)
	for i in range(1, n + 1):
		if a[i] > a[i + 1] and a[i] > a[i - 1]:
			a[i] = max(a[i + 1], a[i - 1])
	cout = 0
	for i in range(len(a) - 1):
		cout += abs(a[i] - a[i + 1])
	return cout + s - sum(a)
x = int(input())
for _ in range(x):
	y = int(input())
	A = list(map(int, input().split()))
	print(sol(A, y))


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

	def fun():
		if n == 1:
			return l[0]
		ans = 0
		for i in range(n):
			if i == 0:
				ans += l[0]
				if l[0] > l[1]:
					l[0] = l[1]
				continue
			if i == n - 1:
				ans += l[-1]
				if l[-2] < l[-1]:
					l[-1] = l[-2]
				continue
			if l[i] > l[i - 1] and l[i] > l[i + 1]:
				ans += l[i] - max(l[i - 1], l[i + 1])
				l[i] = max(l[i - 1], l[i + 1])
				if l[i - 1] < l[i]:
					ans += l[i] - l[i - 1]
				if l[i + 1] < l[i]:
					ans += l[i] - l[i + 1]
			else:
				if l[i - 1] < l[i]:
					ans += l[i] - l[i - 1]
				if l[i + 1] < l[i]:
					ans += l[i] - l[i + 1]
		return ans
	print(fun())


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


t = int(input())

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
for _ in range(t):
	n = int(input())
	dummy = list(map(int, input().split()))
	arr = [0]
	for i in range(n):
		arr.append(dummy[i])
	arr.append(0)
	ans = 0
	for i in range(n + 1):
		ans += abs(arr[i + 1] - arr[i])
	for i in range(1, n + 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			ans -= arr[i] - max(arr[i - 1], arr[i + 1])
	print(ans)


def solve(arr, n, ans):
	if n == 1:
		ans.append(str(arr[0]))
		return
	total = arr[0] + arr[-1]
	for i in range(1, n):
		total += abs(arr[i] - arr[i - 1])
	for i in range(n):
		if i == 0:
			if i + 1 < n and arr[i] > arr[i + 1]:
				total -= arr[i] - arr[i + 1]
				arr[i] = arr[i + 1]
		elif i == n - 1:
			if arr[i] > arr[i - 1]:
				total -= arr[i] - arr[i - 1]
		elif arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			total -= arr[i] - max(arr[i - 1], arr[i + 1])
			arr[i] = max(arr[i - 1], arr[i + 1])
	ans.append(str(total))

def main():
	t = int(input())
	ans = []
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		solve(arr, n, ans)
	print('\n'.join(ans))
main()


import sys, os
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
from math import *
from bisect import *
from collections import defaultdict as dd
from collections import Counter as cc
tc = 1
tc = int(input())
for test in range(1, tc + 1):
	n = int(input())
	a = [0] + inp() + [0]
	ans = a[1]
	for i in range(1, n + 1):
		if a[i - 1] < a[i] and a[i] > a[i + 1]:
			temp = max(a[i - 1], a[i + 1])
			res = a[i] - temp
			ans += res + abs(a[i - 1] - a[i + 1]) - abs(a[i] - a[i - 1])
			a[i] = temp
		else:
			ans += abs(a[i] - a[i + 1])
	print(ans)


n_cases = int(input())
data = []
for _ in range(n_cases):
	n = int(input())
	hist = map(int, input().split())
	data.append((n, tuple(hist)))
for (n, hist) in data:
	base_ugliness = sum((abs(h - last_h) for (last_h, h) in zip(*[[0, *hist, 0][t:] for t in range(2)])))
	modifier = sum((min(b - a, b - c) for (a, b, c) in zip(*[[0, *hist, 0][t:] for t in range(3)]) if b > max(a, c)))
	print(base_ugliness - modifier)


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	if len(arr) == 0:
		print(0)
	elif len(arr) == 1:
		print(arr[0])
	else:
		op = 0
		arr = [0] + arr + [0]
		for i in range(1, n + 1):
			if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
				op += arr[i] - max(arr[i - 1], arr[i + 1])
				arr[i] = max(arr[i - 1], arr[i + 1])
			op += abs(arr[i] - arr[i - 1])
		op += abs(arr[-2] - arr[-1])
		print(op)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(l[0])
	else:
		ans = l[0] + l[-1]
		for i in range(1, n):
			ans += abs(l[i] - l[i - 1])
		for i in range(1, n - 1):
			if l[i] > l[i - 1] and l[i] > l[i + 1]:
				ans -= l[i] - max(l[i - 1], l[i + 1])
		if l[0] > l[1]:
			ans -= l[0] - l[1]
		if l[-1] > l[-2]:
			ans -= l[-1] - l[-2]
		print(ans)
	t -= 1


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
t = int(input())

def isPeak(x, arr):
	return arr[x - 1] <= arr[x] >= arr[x + 1]

def calc(arr):
	ans = 0
	for x in range(1, len(arr) - 1):
		if arr[x] > arr[x - 1]:
			ans += arr[x] - arr[x - 1]
		if arr[x] > arr[x + 1]:
			ans += arr[x] - arr[x + 1]
	return ans
for _ in range(t):
	n = int(input())
	arr = [0] + list(map(int, input().split())) + [0]
	moves = 0
	for x in range(1, n + 1):
		if isPeak(x, arr):
			mx = max(arr[x - 1], arr[x + 1])
			moves += arr[x] - mx
			arr[x] = mx
	print(calc(arr) + moves)


def get_ugliness(a):
	n = len(a)
	ugliness = 0
	delta = 0
	for i in range(n):
		l = 0 if i == 0 else a[i - 1]
		r = 0 if i == n - 1 else a[i + 1]
		x = a[i]
		if x > l:
			ugliness += x - l
		if x > r:
			ugliness += x - r
		if x > l and x > r:
			delta += x - max(l, r)
	return ugliness - delta
n_samples = int(input())
for t in range(n_samples):
	n = int(input())
	a = list(map(int, input().split(' ')))
	assert len(a) == n
	print(get_ugliness(a))


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