The alternating sum of an array A = [A_{1}, A_{2}, \ldots, A_{N}] is defined to be

A_{1} - A_{2} + A_{3} - \ldots + (-1)^{N-1}A_{N}

You are allowed to perform the following operation at most once on A:
Choose a subarray of A of odd length, remove this subarray from the original array, and concatenate it at the end of the remaining array. In other words, pick 1≤ L ≤ R ≤ N such that R-L+1 is odd, and transform A into the array [A_{1}, A_{2}, \ldots, A_{L-1}, A_{R+1}, \ldots, A_{N}, A_{L}, A_{L+1}, \ldots, A_{R}].

For example, if the original array is [1, 2, 3, 4, 5], two possible moves are:
Choose the subarray [1] and move it to the end to obtain [2, 3, 4, 5, 1]
Choose the subarray [2, 3, 4] and move it to the end to obtain [1, 5, 2, 3, 4]

Given that you can perform this operation at most once, what is the maximum possible alternating sum the resulting array can achieve?

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

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

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

For each test case, print a single line containing one integer — the maximum possible alternating sum obtainable after performing the given operation at most once.

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

$1 ≤ T ≤ 10^{5}$
$3 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
2
3
1 5 2
5
1 10 1 5 2

----- Sample Output 1 ------ 
4
13

----- explanation 1 ------ 
- Test Case $1$: Move subarray $[5]$ to the end to obtain the array $[1, 2, 5]$. The alternating sum of this array is $1 - 2 + 5 = 4$, and no larger is possible.

- Test Case $2$: Move subarray $[1]$ starting at index $1$ to the end to obtain the array $[10, 1, 5, 2, 1]$. The alternating sum of this array is $10 - 1 + 5 - 2 + 1 = 13$, and no larger is possible.

Difficulty: HARD
Tags: Preprocessing

Data structures

Range queries
Skill types: Data structures

Range queries

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	suf = 0
	pref = 0
	mxpref = 0
	for i in range(n):
		if i % 2 == 0:
			suf += a[i]
		else:
			suf -= a[i]
	ans = suf
	for i in range(n):
		if i % 2 == 0:
			suf -= a[i]
			pref += a[i]
		else:
			suf += a[i]
			pref -= a[i]
		if i % 2 != n % 2:
			ans = max(ans, pref - suf)
			mxpref = max(mxpref, pref)
		else:
			ans = max(ans, 2 * mxpref - pref - suf)
	print(ans)


from collections import Counter
from functools import reduce
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	suf = [0] * (n + 1)
	f = -1 if n % 2 == 0 else 1
	for i in range(n - 1, -1, -1):
		suf[i] = f * a[i] + suf[i + 1]
		f *= -1
	min_pos = [0] * (n + 1)
	(min_pos[0], min_pos[1]) = (suf[0], suf[1])
	for i in range(n + 1):
		min_pos[i] = min(min_pos[i - 2], suf[i])
	val = suf[0]
	ans = val
	for i in range(n - 1, -1, -1):
		if (n - i + 1) % 2 != 0:
			ans = max(ans, val - 2 * suf[i])
		else:
			ans = max(ans, val - 2 * min_pos[i - 1])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	prefix = [0] * n
	prefix[0] = arr[0]
	for i in range(1, n):
		if i % 2 == 0:
			prefix[i] = prefix[i - 1] + arr[i]
		else:
			prefix[i] = prefix[i - 1] - arr[i]
	ind = 0
	if n % 2 == 0:
		ind = 1
	maxsum = 0
	while ind < n:
		maxsum = max(maxsum, prefix[ind])
		ind += 2
	res = 2 * maxsum - prefix[n - 1]
	print(res)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l2 = []
	(o, e) = (0, 0)
	ans = 0
	for j in range(n):
		if j % 2 == 0:
			o += l[j]
		else:
			e += l[j]
		l2.append((o, e))
	if n % 2 == 1:
		for j in range(n):
			if j % 2 == 0:
				(o, e) = l2[j]
				(o, e) = (o + l2[-1][1] - e, e + l2[-1][0] - o)
			else:
				(o, e) = l2[j - 1]
				(o, e) = (o + l2[-1][1] - e, e + l2[-1][0] - o)
			temp = o - e
			ans = max(ans, temp)
	else:
		(o, e) = l2[-1]
		ans = e - o
		for j in range(1, n):
			if j % 2 == 1:
				(o, e) = l2[j]
				(o, e) = (o + l2[-1][1] - e, e + l2[-1][0] - o)
			else:
				(o, e) = l2[j - 1]
				(o, e) = (o + l2[-1][1] - e, e + l2[-1][0] - o)
			temp = o - e
			ans = max(ans, temp)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [0] * (n + 1)
	for i in range(n):
		dp[i + 1] += a[i] + dp[i] if i % 2 == 0 else -a[i] + dp[i]
	m = dp[-1]
	for i in range(n):
		s1 = dp[i]
		s2 = dp[-1] - dp[i + 1]
		if i % 2:
			m = max(m, s1 - s2 - a[i]) if (n - i - 1) % 2 == 0 else max(m, s1 - s2 + a[i])
		else:
			m = max(m, s1 - s2 + a[i]) if (n - i - 1) % 2 == 0 else max(m, s1 - s2 - a[i])
	print(m)


import math
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
for _ in range(I()):
	n = I()
	a = L()
	dp = [0] * (n + 1)
	for i in range(n):
		if i % 2 == 0:
			dp[i + 1] += a[i] + dp[i]
		else:
			dp[i + 1] += -a[i] + dp[i]
	m = dp[-1]
	for i in range(n):
		s1 = dp[i]
		s2 = dp[-1] - dp[i + 1]
		if i % 2 == 1:
			if (n - i - 1) % 2 == 0:
				m = max(m, s1 - s2 - a[i])
			else:
				m = max(m, s1 - s2 + a[i])
		elif (n - i - 1) % 2 == 0:
			m = max(m, s1 - s2 + a[i])
		else:
			m = max(m, s1 - s2 - a[i])
	print(m)


from itertools import permutations as per
from math import factorial as fact
from difflib import SequenceMatcher
import bisect
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	for i in range(1, n):
		if i % 2:
			a[i] = a[i - 1] - a[i]
		else:
			a[i] = a[i - 1] + a[i]
	ans = a[-1]
	if n % 2:
		for i in range(1, n, 2):
			ans = max(ans, a[i - 1] - (a[-1] - a[i - 1]))
	else:
		for i in range(2, n, 2):
			ans = max(ans, a[i - 1] - (a[-1] - a[i - 1]))
		ans = max(ans, -a[-1])
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	pre = [0] * n
	suff = [0] * n
	pre[0] = arr[0]
	if (n - 1) % 2 == 0:
		suff[n - 1] = arr[n - 1]
	else:
		suff[n - 1] = -arr[n - 1]
	for i in range(1, n):
		if i % 2 == 0:
			pre[i] = pre[i - 1] + arr[i]
		else:
			pre[i] = pre[i - 1] - arr[i]
	ans = pre[-1]
	for i in range(n - 2, -1, -1):
		if i % 2 == 0:
			suff[i] = suff[i + 1] + arr[i]
		else:
			suff[i] = suff[i + 1] - arr[i]
	ans = max(ans, -suff[0])
	for i in range(n - 2, 0, -2):
		ans = max(ans, pre[i - 1] - suff[i])
	print(ans)


for tc in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	if n % 2 == 0:
		sp1 = []
		sp2 = []
		for x in range(len(ls)):
			if x % 2 == 0:
				if len(sp1) == 0:
					sp1.append(ls[x])
				else:
					sp1.append(sp1[-1] + ls[x])
			elif len(sp2) == 0:
				sp2.append(ls[x])
			else:
				sp2.append(sp2[-1] + ls[x])
		ma = max(sp1[-1] - sp2[-1], sp2[-1] - sp1[-1])
		for x in range(len(sp1) - 1):
			ma = max(ma, sp2[-1] - sp2[x] + sp1[x] - (sp1[-1] - sp1[x] + sp2[x]))
		print(ma)
	else:
		fir = ls[0]
		sp1 = []
		sp2 = []
		for x in range(1, len(ls)):
			if x % 2 == 0:
				if len(sp1) == 0:
					sp1.append(ls[x])
				else:
					sp1.append(sp1[-1] + ls[x])
			elif len(sp2) == 0:
				sp2.append(ls[x])
			else:
				sp2.append(sp2[-1] + ls[x])
		su1 = sp1[-1]
		su2 = sp2[-1]
		ma = fir + su1 - su2
		ma = max(ma, fir + su2 - su1)
		for x in range(len(sp1) - 1):
			ma = max(ma, fir + sp1[x] + sp2[-1] - sp2[x] - (sp1[-1] - sp1[x] + sp2[x]))
		print(ma)


from sys import stdin
input = stdin.readline
from collections import Counter
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	s = 0
	ai = [0]
	for i in range(n):
		if i % 2 == 0:
			s = s + li[i]
		else:
			s = s - li[i]
		ai.append(s)
	ans = s
	for i in range(1, n):
		if (n + i) % 2:
			ans = max(ans, 2 * ai[i - 1] - ai[n])
	print(ans)


for i in range(int(input())):
	n = int(input())
	b = [int(x) for x in input().split()]
	if n == 1:
		print(b[0])
		continue
	if n % 2 == 1:
		pre = {}
		su = 0
		for i in range(n - 1, -1, -1):
			if i % 2 == 0:
				su += -1 * b[i]
			else:
				su += b[i]
			pre[i + 1] = su
		ans = []
		su = 0
		for i in range(n):
			if i % 2 == 1:
				ans.append(su + pre[i + 1])
			if i % 2 == 0:
				su += b[i]
			else:
				su += -1 * b[i]
		ans.append(su)
		print(max(ans))
	else:
		pre = {}
		su = 0
		for i in range(n - 1, -1, -1):
			if i % 2 == 0:
				su += -1 * b[i]
			else:
				su += b[i]
			pre[i + 1] = su
		ans = []
		su = 0
		for i in range(n):
			if i % 2 == 0:
				ans.append(su + pre[i + 1])
			if i % 2 == 0:
				su += b[i]
			else:
				su += -1 * b[i]
		ans.append(su)
		print(max(ans))


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	s = 0
	i = 0
	while i < n:
		s += arr[i]
		i += 1
		if i < n:
			s -= arr[i]
			i += 1
	mx = 0
	if n % 2 == 0:
		curr = 0
		i = 1
		while i <= n:
			if i % 2 == 0:
				curr += arr[-i]
				if curr < mx:
					mx = curr
			else:
				curr -= arr[-i]
			i += 1
	else:
		curr = 0
		i = 1
		while i <= n:
			if i % 2 == 0:
				curr -= arr[-i]
				if curr < mx:
					mx = curr
			else:
				curr += arr[-i]
			i += 1
	return s + 2 * abs(mx)
for _ in range(int(input())):
	print(main())


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	maxx = 0
	ans = 0
	prefix = []
	if n == 1:
		print(arr[0])
		continue
	for j in range(n):
		if not j % 2:
			ans += arr[j]
		else:
			ans -= arr[j]
		prefix.append(ans)
	maxx = prefix[-1]
	for i in range(n - 1):
		x = -(prefix[-1] - prefix[i])
		if i != 0:
			x += prefix[i - 1]
		if n % 2:
			x += arr[i]
		else:
			x -= arr[i]
		maxx = max(x, maxx)
	print(maxx)


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():
	harshan = inp()
	harshal = li()
	harshaans = 0
	for i in range(harshan):
		if i % 2 == 0:
			harshaans += harshal[i]
		else:
			harshaans -= harshal[i]
	harshas = 0
	cur = harshaans
	for i in range(harshan):
		if i % 2 == 0:
			x = cur - harshal[i]
		else:
			x = cur + harshal[i]
		x -= harshas
		if harshan % 2 == 0:
			harshaans = max(harshaans, harshas - x - harshal[i])
		else:
			harshaans = max(harshaans, harshas - x + harshal[i])
		if i % 2 == 0:
			harshas += harshal[i]
		else:
			harshas -= harshal[i]
	pr(harshaans)
for _ in range(inp()):
	solve()


import heapq

class MaxHeap:

	def __init__(self):
		self._heap = []
		heapq.heapify(self._heap)

	def insert(self, it):
		heapq.heappush(self._heap, -it)

	def peek(self):
		val = self._heap[0]
		return -val

def solve(A, n):
	pref = [0] * (n + 1)
	for i in range(1, n + 1):
		pref[i] = pref[i - 1]
		if i % 2:
			pref[i] += A[i - 1]
		else:
			pref[i] -= A[i - 1]
	suff = [0] * (n + 2)
	for i in range(n, 0, -1):
		suff[i] = A[i - 1] - suff[i + 1]
	ans = suff[1]
	heaps_1 = [MaxHeap(), MaxHeap()]
	heaps_2 = [MaxHeap(), MaxHeap()]
	for R in range(1, n + 1):
		last = n - R
		heaps_1[R % 2].insert(pref[R - 1] - suff[R])
		heaps_2[R % 2].insert(pref[R - 1] + suff[R])
		max1 = heaps_1[R % 2].peek()
		max2 = heaps_2[R % 2].peek()
		if R % 2:
			if last % 2:
				ans = max(ans, max1)
			else:
				ans = max(ans, max2 + 2 * suff[R + 1])
		elif last % 2:
			ans = max(ans, max2)
		else:
			ans = max(max1 - 2 * suff[R + 1], ans)
	return ans
for case in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	ans = solve(A, n)
	print(ans)


T = int(input())
for tc in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	asum = 0
	for i in range(n):
		if i % 2 == 0:
			asum = asum + A[i]
		else:
			asum = asum - A[i]
	res = 0
	if n % 2 == 0:
		a = 0
		for i in range(n):
			if i % 2 == 0:
				a += A[i]
			else:
				a -= A[i]
				t = 2 * a - asum
				res = max(res, t)
		a = 0
		for i in range(n):
			if (n - 1 - i) % 2 == 0:
				a += A[n - 1 - i]
				t = asum - 2 * a
				res = max(res, t)
			else:
				a -= A[n - 1 - i]
	else:
		a = 0
		for i in range(n):
			if i % 2 == 0:
				a += A[i]
				t = 2 * a - asum
				res = max(res, t)
			else:
				a -= A[i]
		a = 0
		for i in range(n):
			if (n - 1 - i) % 2 == 0:
				a += A[n - 1 - i]
			else:
				a -= A[n - 1 - i]
				t = asum - 2 * a
				res = max(res, t)
	print(res)


import math
import sys
input = sys.stdin.readline
SD = lambda : input().rstrip()
AX = lambda : int(SD())
FR = lambda : map(int, SD().split())
YH = lambda : list(FR())
ikj4 = 1000000007
ikj5 = 998244353
for _ in range(AX()):
	sxwqe = AX()
	bghyt = YH()
	zxsa = [0] * (sxwqe + 1)
	for nmjik in range(sxwqe):
		if nmjik % 2 == 0:
			zxsa[nmjik + 1] += bghyt[nmjik] + zxsa[nmjik]
		else:
			zxsa[nmjik + 1] += -bghyt[nmjik] + zxsa[nmjik]
	okilp = zxsa[-1]
	for nmjik in range(sxwqe):
		axsde3 = zxsa[nmjik]
		axsde4 = zxsa[-1] - zxsa[nmjik + 1]
		if nmjik % 2 == 1:
			if (sxwqe - nmjik - 1) % 2 == 0:
				okilp = max(okilp, axsde3 - axsde4 - bghyt[nmjik])
			else:
				okilp = max(okilp, axsde3 - axsde4 + bghyt[nmjik])
		elif (sxwqe - nmjik - 1) % 2 == 0:
			okilp = max(okilp, axsde3 - axsde4 + bghyt[nmjik])
		else:
			okilp = max(okilp, axsde3 - axsde4 - bghyt[nmjik])
	print(okilp)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	eve = 0
	odd = 0
	for i in range(n):
		if i % 2 == 1:
			eve += l[i]
		else:
			odd += l[i]
	ans = odd - eve
	(a, b) = (0, 0)
	for i in range(n - 1):
		if i % 2 == 1:
			if (n - i - 1) % 2 == 1:
				x = b - a - (eve - odd)
				eve -= l[i]
				a += l[i]
			else:
				x = b - a - (eve - odd + 2 * l[i])
				eve -= l[i]
				a += l[i]
		elif (n - i - 1) % 2 == 1:
			x = b - a + eve - odd
			odd -= l[i]
			b += l[i]
		else:
			x = b - a + eve - odd + 2 * l[i]
			odd -= l[i]
			b += l[i]
		ans = max(ans, x)
	print(ans)


from sys import stdin
input = stdin.readline

def answer():
	if n & 1 == 0:
		what = 0
	else:
		what = 1
	value = a[0]
	for i in range(1, n):
		if i & 1 == 0:
			value += a[i]
		else:
			value -= a[i]
	(s, ans) = (0, value)
	for i in range(n - 1, 0, -1):
		if what == 0:
			s -= a[i]
		else:
			s += a[i]
		if n - i & 1 == 0:
			ans = max(ans, value - s - s)
		what ^= 1
	if n & 1 == 0:
		what = 0
	else:
		what = 1
	if what == 0:
		s = -a[-1]
	else:
		s = a[-1]
	what ^= 1
	for i in range(n - 2, -1, -1):
		if what == 0:
			s -= a[i]
		else:
			s += a[i]
		if n - i & 1 == 0:
			ans = max(ans, value - s - s)
		what ^= 1
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answer())


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		if i & 1 == 1:
			a[i] = -a[i]
	pr = [0] * n
	pr[0] = a[0]
	ma = [0] * n
	ma[0] = [a[0], 1]
	for i in range(1, n):
		pr[i] = pr[i - 1] + a[i]
		if ma[i - 1][0] < pr[i]:
			ma[i] = [pr[i], i + 1]
		else:
			ma[i] = ma[i - 1]
	total_sum = pr[n - 1]
	ans = total_sum
	for i in range(n - 1, 0, -1):
		end_sum = pr[n - 1] - pr[i - 1]
		start_sum = ma[i - 1][0]
		start_length = ma[i - 1][1]
		remaining_sum = total_sum - (end_sum + start_sum)
		if (n - (start_length + (n - i))) % 2 != 0 or n - (start_length + (n - i)) == 0:
			if (n - i) % 2 != 0:
				remaining_sum = -1 * remaining_sum
			if remaining_sum == 0 and start_length % 2 != 0:
				start_sum = -1 * start_sum
			ans = max(ans, start_sum + remaining_sum + -1 * end_sum)
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	for i in range(n):
		if i % 2:
			s -= l[i]
		else:
			s += l[i]
	ans = 0
	if n % 2 == 0:
		k1 = 0
		for i in range(n):
			if i % 2:
				k1 -= l[i]
				ans = max(ans, 2 * k1 - s)
			else:
				k1 += l[i]
		k3 = 0
		for i in range(n - 1, -1, -1):
			if i % 2:
				k3 -= l[i]
			else:
				k3 += l[i]
				ans = max(ans, s - 2 * k3)
	else:
		k1 = 0
		for i in range(n):
			if i % 2:
				k1 -= l[i]
			else:
				k1 += l[i]
				ans = max(ans, 2 * k1 - s)
		k3 = 0
		for i in range(n - 1, -1, -1):
			if i % 2:
				k3 -= l[i]
				ans = max(ans, s - 2 * k3)
			else:
				k3 += l[i]
	print(ans)


from sys import stdin, stdout, setrecursionlimit as srl
from threading import stack_size
from collections import deque, defaultdict as dd
from math import gcd, ceil, sqrt
from bisect import bisect_left as lb
from bisect import bisect_right as rb
flush = stdout.flush
p = int(1000000000.0 + 7)
tc = 1
tc = int(input())
for _ in range(1, tc + 1):
	n = int(input())
	a = list(map(int, input().split()))
	suf = a.copy()
	for i in range(n - 2, -1, -1):
		suf[i] -= suf[i + 1]
	ans = suf[0]
	if n % 2 == 1:
		mn = float('-inf')
		for i in range(1, n, 2):
			mn = max(mn, suf[i])
		ans = max(ans, suf[0] + 2 * mn)
		dp = [-1 for i in range(n)]
		dp[0] = a[0]
		dp[1] = a[1]
		for i in range(2, n):
			dp[i] = max(a[i], a[i] - a[i - 1] + dp[i - 2])
		mx = float('-inf')
		for i in range(2, n, 2):
			mx = max(mx, suf[0] - 2 * suf[i] + 2 * dp[i - 1])
		ans = max(ans, mx)
	if n % 2 == 0:
		mn = float('inf')
		for i in range(2, n, 2):
			mn = min(mn, suf[i])
		ans = max(ans, suf[0] - 2 * mn)
		dp = [-1 for i in range(n)]
		dp[0] = a[0]
		dp[1] = a[1]
		for i in range(2, n):
			dp[i] = max(a[i], a[i] - a[i - 1] + dp[i - 2])
		mx = float('-inf')
		for i in range(1, n, 2):
			mx = max(mx, suf[0] + 2 * suf[i] - 2 * dp[i - 1])
		ans = max(ans, mx)
	print(ans)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	sys.stderr = open('error.txt', 'w')
depth = 200001
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
linp = lambda : list(minp())
minp = lambda : map(int, input().split())
from math import inf, ceil, sqrt, log2, gcd
from collections import defaultdict, deque
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def expo(a, b):
	if not b:
		return 1
	v = expo(a, b // 2)
	v = v * v % mod
	if b % 2:
		v = v * a % mod
	return v

def modinv(a, b):
	d = expo(b, mod - 2)
	v = a * d % mod
	return v

def checkPrime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	a = [0] + linp()
	for i in range(n + 1):
		if i % 2 == 0:
			a[i] = -a[i]
	for i in range(1, n + 1):
		a[i] += a[i - 1]
	ans = a[n]
	if n % 2 == 0:
		for i in range(1, n + 1, 2):
			val = a[i - 1] + -(a[n] - a[i - 1])
			ans = max(ans, val)
		for i in range(2, n + 1, 2):
			val = a[i] + -(a[n] - a[i])
			ans = max(ans, val)
	else:
		for i in range(1, n + 1, 2):
			val = a[i] + -(a[n] - a[i])
			ans = max(ans, val)
		for i in range(2, n + 1, 2):
			val = a[i - 1] + -(a[n] - a[i - 1])
			ans = max(ans, val)
	print(ans)


from sys import stdin, stdout
from collections import Counter
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
for _ in range(nmbr()):
	n = nmbr()
	a = lst()
	pre = [0] * n
	pre[0] = a[0]
	for i in range(n):
		if i & 1:
			pre[i] = pre[i - 1] - a[i]
		else:
			pre[i] = pre[i - 1] + a[i]
	suf = [0] * n
	if n - 1 & 1:
		suf[-1] = -a[-1]
	else:
		suf[-1] = a[-1]
	for i in range(n - 2, -1, -1):
		if i & 1:
			suf[i] = suf[i + 1] - a[i]
		else:
			suf[i] = suf[i + 1] + a[i]
	if n & 1:
		ans = pre[-1]
		for i in range(n):
			left = right = 0
			if i & 1:
				if i - 1 >= 0:
					left = pre[i - 1]
				right = suf[i]
				ans = max(ans, left - right)
	else:
		ans = pre[-1]
		for i in range(n):
			left = right = 0
			if i & 1 == 0:
				if i - 1 >= 0:
					left = pre[i - 1]
				right = suf[i]
				ans = max(ans, left - right)
	print(ans)


import sys
import math
import random
import heapq
input = sys.stdin.readline

def pow(a, n, m):
	if n == 0:
		return 1
	x = pow(a, n // 2, m)
	if n % 2 == 0:
		return x * x % m
	else:
		return x * x * a % m

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a

def bs(arr, le, ri):
	l = 0
	arr.sort()
	r = len(arr) - 1
	ans = 10000000
	while l <= r:
		m = (l + r) // 2
		if arr[m] >= le and arr[m] <= ri:
			ans = arr[m]
			r = m - 1
		elif arr[m] < le:
			l = m + 1
		else:
			r = m - 1
	return ans
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if i % 2 == 0:
			ans += a[i]
		else:
			ans -= a[i]
	an = 0
	c = 0
	for i in range(n - 2, -1, -2):
		if i % 2 == 0:
			c += a[i] - a[i + 1]
		else:
			c -= a[i] - a[i + 1]
		an = min(an, c)
	print(ans - 2 * an)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(pos, neg) = ([0] * (n + 1), [0] * (n + 1))
	for i in range(n - 1, -1, -1):
		if i % 2 == 0:
			pos[i] = pos[i + 1] + a[i]
			neg[i] = neg[i + 1]
		else:
			pos[i] = pos[i + 1]
			neg[i] = neg[i + 1] + a[i]
	ans = pos[0] - neg[0]
	fans = pos[0] - neg[0]
	if n % 2 == 0:
		for i in range(0, n, 2):
			temp = ans - 2 * pos[i] + 2 * neg[i]
			fans = max(fans, temp)
	else:
		for i in range(1, n, 2):
			temp = ans - 2 * pos[i] + 2 * neg[i]
			fans = max(fans, temp)
	print(fans)