You and your friend decide to play a game using a stack consisting of N bricks. In this game, you can alternatively remove 1, 2 or 3 bricks from the top, and the numbers etched on the removed bricks are added to your score. You have to play so that you obtain the maximum possible score. It is given that your friend will also play optimally and you make the first move.  

As an example, bricks are numbered $arr=[1,2,3,4,5]$.  You can remove either $\left[1\right]=1$, $[1,2]=3$ or $[1,2,3]=6$.  For your friend, your moves would leave the options of $\mbox{1}$ to $3$ elements from $[2,3,4]=9$ leaving $5$ for you (total score = $\boldsymbol{6}$), $[3,4,5]=12$ or $[4,5]=9$.  In this case, it will never be optimal for your friend to take fewer than the maximum available number of elements.  Your maximum possible score is $\boldsymbol{6}$, achievable two ways: $\mbox{1}$ first move and $5$ the second, or $[1,2,3]$ in your first move.  

Function Description  

Complete the bricksGame function in the editor below.  It should return an integer that represents your maximum possible score.  

bricksGame has the following parameter(s):  

arr:  an array of integers  

Input Format

The first line will contain an integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases.  

Each of the next $\boldsymbol{\boldsymbol{t}}$ pairs of lines are in the following format: 

The first line contains an integer $n$, the number of bricks in $\textbf{arr}$. 

The next line contains $n$ space-separated integers $arr[i].  

Constraints

$1\leq t\leq5$ 

$1\leq n\leq10^5$ 

$0\leq arr[i]\leq10^9$    

Output Format

For each test case, print a single line containing your maximum score.

Sample Input
2
5
999 1 1 1 0
5
0 1 1 1 999

Sample Output
1001
999

Explanation

In first test case, you will pick 999,1,1. If you play in any other way, you will not get a score of 1001. 

In second case, best option will be to pick up the first brick (with 0 score) at first. Then your friend  will choose the next three blocks, and you will get the last brick.

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
INF = 10 ** 18

def one_test():
	n = int(input())
	a = list(reversed(list(map(int, input().split()))))
	dp = [0] * (n + 1)
	for i in range(n):
		take = 0
		dp[i + 1] = -INF
		for j in range(i, max(i - 3, -1), -1):
			take += a[j]
			dp[i + 1] = max(dp[i + 1], take - dp[j])
	return (sum(a) + dp[n]) // 2
t = int(input())
for i in range(t):
	print(one_test())


import sys

def read_numbers(line=None):
	if line is None:
		line = sys.stdin.readline()
	return [int(x) for x in line.split()]

def get(l, i, default=0):
	try:
		return l[i]
	except IndexError:
		return default

def calculate_best_result(stack, best_results, best_moves, i):
	took_one = get(stack, i) + max([0] + [get(best_results, i + 1 + move) for move in get(best_moves, i + 1, [])])
	took_two = get(stack, i) + get(stack, i + 1) + max([0] + [get(best_results, i + 2 + move) for move in get(best_moves, i + 2, [])])
	took_three = get(stack, i) + get(stack, i + 1) + get(stack, i + 2) + max([0] + [get(best_results, i + 3 + move) for move in get(best_moves, i + 3, [])])
	scores = sorted([(took_one, 1), (took_two, 2), (took_three, 3)], reverse=True)
	(best_result, best_move) = scores[0]
	best_moves = set([best_move])
	for (score, move) in scores[1:]:
		if score == best_results:
			best_moves.add(move)
	return (best_result, best_moves)

def game(stack):
	best_results = [0] * len(stack)
	best_moves = [set()] * len(stack)
	for i in range(len(stack) - 1, -1, -1):
		(result, move) = calculate_best_result(stack, best_results, best_moves, i)
		best_results[i] = result
		best_moves[i] = move
	return best_results[0]
test_cases = read_numbers()[0]
for t in range(test_cases):
	n = read_numbers()[0]
	stack = read_numbers()
	print(game(stack))


for _ in range(int(input())):
	n = int(input())
	v = [int(e) for e in input().split()]
	v.reverse()
	x = [0] * n
	sums = [0] * n
	for (i, vi) in enumerate(v):
		sums[i] = sums[i - 1] + vi
	x[0] = v[0]
	x[1] = x[0] + v[1]
	x[2] = x[1] + v[2]
	for i in range(3, n):
		x[i] = max(sums[i - 1] - x[i - 1] + v[i], sums[i - 2] - x[i - 2] + v[i] + v[i - 1], sums[i - 3] - x[i - 3] + v[i] + v[i - 1] + v[i - 2])
	print(x[n - 1])


T = int(input())
(S, M) = ([], [])

def getMin(s):
	x = min(M[s + 1], M[s + 2], M[s + 3])
	for i in range(1, 4):
		if x == M[s + i]:
			return s + i
	return -1
for _ in range(T):
	N = int(input())
	S = [int(x) for x in input().split()]
	if N <= 3:
		print(sum(S))
		continue
	M = [0] * (N + 4)
	M[N - 1] = S[N - 1]
	M[N - 2] = M[N - 1] + S[N - 2]
	M[N - 3] = M[N - 2] + S[N - 3]
	for i in range(N - 4, -1, -1):
		M[i] = max(S[i] + M[getMin(i + 1)], sum(S[i:i + 2]) + M[getMin(i + 2)], sum(S[i:i + 3]) + M[getMin(i + 3)])
	print(M[0])


T = int(input())
for i in range(T):
	N = int(input())
	numbers = [int(x) for x in input().split()]
	if N <= 3:
		print(sum(numbers))
		continue
	numbers = numbers + [0, 0, 0, 0, 0]
	numbers[N + 3] = numbers[N - 3]
	numbers[N + 4] = numbers[N - 2]
	numbers[N - 2] += numbers[N - 1]
	numbers[N - 3] += numbers[N - 2]
	for j in range(N - 4, -1, -1):
		cur_numbers = [numbers[j], numbers[j] + numbers[N + 3], numbers[j] + numbers[N + 3] + numbers[N + 4]]
		cur_minim = [min(numbers[j + 2], numbers[j + 3], numbers[j + 4]), min(numbers[j + 3], numbers[j + 4], numbers[j + 5]), min(numbers[j + 4], numbers[j + 5], numbers[j + 6])]
		numbers[N + 4] = numbers[N + 3]
		numbers[N + 3] = numbers[j]
		numbers[j] = max(cur_numbers[0] + cur_minim[0], cur_numbers[1] + cur_minim[1], cur_numbers[2] + cur_minim[2])
	print(numbers[0])


def best(Bs):
	if len(Bs) < 4:
		return sum(Bs)
	(bb, s) = ([], 0)
	for i in range(3):
		s += Bs[i]
		bb.append(s)
	for i in range(3, len(Bs)):
		s += Bs[i]
		bb.append(s - min(bb[-3:]))
	return bb[-1]
T = int(input())
for t in range(T):
	N = int(input())
	Bs = [int(_) for _ in input().split(' ')]
	print(best(Bs[::-1]))


T = int(input())
for t in range(T):
	n = int(input())
	a = list(reversed(list(map(int, input().split()))))
	sums = [0] * n
	sums[0] = a[0]
	for i in range(1, n):
		sums[i] = sums[i - 1] + a[i]
	dp = [0] * n
	dp[0] = a[0]
	dp[1] = a[0] + a[1]
	dp[2] = a[0] + a[1] + a[2]
	for i in range(3, n):
		dp[i] = max([a[i] + sums[i - 1] - dp[i - 1], a[i] + a[i - 1] + sums[i - 2] - dp[i - 2], a[i] + a[i - 1] + a[i - 2] + sums[i - 3] - dp[i - 3]])
	print(dp[n - 1])


class BrickPuzzle:
	bricks = []
	best = {}
	numberOfBricks = 0
	maxToTake = 3

	def __init__(self, bricks):
		assert 0 <= len(bricks) <= 10 ** 5
		self.bricks = bricks
		self.numberOfBricks = len(bricks)
		self.calculate()

	def takeBricks(self, index, n):
		total = 0
		while index >= 0 and n > 0:
			total += self.bricks[index]
			index -= 1
			n -= 1
		if index - n >= 0:
			newIndex = index - n - self.best[index - n][1]
			if newIndex >= 0:
				total += self.best[newIndex][0]
		return total

	def calculate(self):
		for brickIndex in range(self.numberOfBricks):
			bestTotal = 0
			bestChoice = 1
			for numberTaken in range(1, self.maxToTake + 1, 1):
				amount = self.takeBricks(brickIndex, numberTaken)
				if amount > bestTotal:
					bestTotal = amount
					bestChoice = numberTaken
			self.best[brickIndex] = [bestTotal, bestChoice]

	def getBestScore(self, brickNumber):
		assert 1 <= brickNumber <= self.numberOfBricks
		return self.best[brickNumber - 1][0]
t = int(input())
for i in range(t):
	numberOfBricks = int(input())
	numbersOnBricks = input().strip().split(' ')
	bricks = []
	for brick in numbersOnBricks:
		bricks.append(int(brick))
	bricks.reverse()
	puzzle = BrickPuzzle(bricks)
	print(puzzle.getBestScore(numberOfBricks))


for i in range(int(input())):
	t = int(input())
	a = [int(e) for e in input().split()]
	d = {t - 3: a[t - 3] + a[t - 2] + a[t - 1], t - 2: a[t - 2] + a[t - 1], t - 1: a[t - 1], t: 0}

	def max_score(n):
		if n in d:
			return d[n]
		else:
			r = max(a[n] - max_score(n + 1), a[n] + a[n + 1] - max_score(n + 2), a[n] + a[n + 1] + a[n + 2] - max_score(n + 3))
			d[n] = r
			return r
	for j in reversed(range(t)):
		diff = max_score(j)
	print((sum(a) + diff) // 2)


cases = int(input())
for i in range(cases):
	input()
	bricks = [int(x) for x in input().strip().split()]
	bricks.reverse()
	sums = [0] * len(bricks)
	sums[0] = bricks[0]
	for j in range(1, len(bricks)):
		sums[j] = bricks[j] + sums[j - 1]
	dp = [0] * len(bricks)
	dp[0] = bricks[0]
	dp[1] = bricks[1] + dp[0]
	dp[2] = bricks[2] + dp[1]
	for i in range(3, len(bricks)):
		dp[i] = max(bricks[i] + sums[i - 1] - dp[i - 1], bricks[i] + bricks[i - 1] + sums[i - 2] - dp[i - 2], bricks[i] + bricks[i - 1] + bricks[i - 2] + sums[i - 3] - dp[i - 3])
	print(dp[len(bricks) - 1])


def crea(a):
	global mo, v
	n = len(a)
	mo = [0] * (n + 1)
	v = [0] * (n + 1)
	for i in range(3):
		mo[i + 1] = i + 1
		v[i + 1] = sum((a[k] for k in range(0, i + 1)))
	for j in range(4, n + 1):
		p = [sum((a[j - i - 1] for i in range(k))) + v[j - k - mo[j - k]] for k in range(1, 4)]
		ok = max(p)
		for u in range(3):
			if p[u] == ok:
				mo[j] = u + 1
				v[j] = ok
	return mo

def haz():
	global a
	nt = int(input())
	for t in range(nt):
		n = int(input())
		line = input()
		a = [int(x) for x in line.split()]
		a.reverse()
		crea(a)
		print(v[n])
	return 'done'
haz()


import sys
T = int(sys.stdin.readline().strip())
for t in range(T):
	sys.stdin.readline()
	A = list(map(lambda x: int(x.strip()), sys.stdin.readline().split()))
	A.reverse()
	B = [0] * len(A)
	C = [0] * len(A)
	C[0] = A[0]
	C[1] = A[0] + A[1]
	C[2] = A[0] + A[1] + A[2]
	B[0] = A[0]
	for i in range(1, len(A)):
		B[i] = B[i - 1] + A[i]
	for i in range(3, len(A)):
		m1 = B[i - 1] - C[i - 1] + A[i]
		m2 = B[i - 2] - C[i - 2] + A[i] + A[i - 1]
		m3 = B[i - 3] - C[i - 3] + A[i] + A[i - 1] + A[i - 2]
		C[i] = max(m1, m2, m3)
	print(C[-1])


def calculate(bricks):
	bricks.reverse()
	numbricks = len(bricks)
	sumx = [bricks[0]] + (numbricks - 1) * [-1]
	for x in range(1, numbricks):
		sumx[x] = bricks[x] + sumx[x - 1]
	dp = [sumx[0], sumx[1], sumx[2]] + (numbricks - 3) * [-1]
	for x in range(3, numbricks):
		dp[x] = max(bricks[x] + sumx[x - 1] - dp[x - 1], bricks[x] + bricks[x - 1] + sumx[x - 2] - dp[x - 2], bricks[x] + bricks[x - 1] + bricks[x - 2] + sumx[x - 3] - dp[x - 3])
	return dp[-1]
testcases = int(input())
for x in range(testcases):
	numbricks = int(input())
	bricks = input().split(' ')
	bricks2 = [int(x2) for x2 in bricks]
	print(calculate(bricks2))


test = int(input())

def getOptimalMap(lst, index, dic, sum_array, length):
	if dic[index] is not None:
		return dic[index]
	if length - index <= 3:
		dic[index] = sum_array[index]
	else:
		m = None
		for i in range(1, 4):
			x = getOptimalMap(lst, index + i, dic, sum_array, length)
			val = sum_array[index] - x
			if m is None:
				m = val
			elif val > m:
				m = val
		dic[index] = m
	return dic[index]
while test:
	test -= 1
	n = int(input())
	lst = [int(x) for x in input().strip().split(' ')]
	length = len(lst)
	dic = [None] * length
	dic[length - 1] = lst[-1]
	sum_array = [0] * length
	tmp = 0
	for i in reversed(range(length)):
		sum_array[i] = tmp + lst[i]
		tmp = sum_array[i]
	for i in range(2, len(lst) + 1):
		getOptimalMap(lst, length - i, dic, sum_array, length)
	print(dic[0])


__author__ = 'Satya'

def play_game():
	tc = int(input())
	for _ in range(tc):
		n = int(input())
		numbers = [int(x) for x in input().split()]
		if n < 4:
			return sum(numbers)
		total = [0] * n
		total[n - 1] = numbers[n - 1]
		for i in range(n - 2, -1, -1):
			total[i] = total[i + 1] + numbers[i]
		output = [0] * n
		output[n - 1] = numbers[n - 1]
		output[n - 2] = numbers[n - 2] + output[n - 1]
		output[n - 3] = numbers[n - 3] + output[n - 2]
		for i in range(n - 4, -1, -1):
			a = total[i] - output[i + 1]
			b = total[i] - output[i + 2]
			c = total[i] - output[i + 3]
			if a >= b and a >= c:
				output[i] = a
			elif b >= a and b >= c:
				output[i] = b
			else:
				output[i] = c
		print(output[0])
play_game()


def solve(stack):
	max_score_at = {len(stack): 0}
	for (i, num) in reversed(list(enumerate(stack))):
		possible_scores = []
		for n_taken in (1, 2, 3):
			if i + n_taken - 1 >= len(stack):
				break
			score = sum(stack[i:i + n_taken]) - max_score_at[i + n_taken]
			possible_scores.append(score)
		max_score_at[i] = max(possible_scores)
	max_delta = max_score_at[0]
	return (max_delta + sum(stack)) // 2
T = int(input())
cases = []
for _ in range(T):
	input()
	cases.append([int(x) for x in input().split(' ')])
for stack in cases:
	print(solve(stack))


sums = {}

def summ(i):
	total = 0
	for k in range(i + 1):
		total = total + int(a[k])
	return total

def do(n):
	if n < 4:
		return summ(len(a) - 1)
	else:
		dp = {0: int(a[0]), 1: int(a[0]) + int(a[1]), 2: int(a[0]) + int(a[1]) + int(a[2])}
		k = 3
		while k < n:
			dp[k] = max(sums[k - 1] - dp[k - 1] + int(a[k]), sums[k - 2] - dp[k - 2] + int(a[k]) + int(a[k - 1]), sums[k - 3] - dp[k - 3] + int(a[k]) + int(a[k - 1]) + int(a[k - 2]))
			k += 1
		return dp[k - 1]
T = int(input())
for x in range(T):
	N = int(input())
	a = input().split(' ')
	a.reverse()
	sums = {}
	total = 0
	i = 0
	for b in a:
		total = total + int(b)
		sums[i] = total
		i += 1
	print(do(N))


sums = {}

def summ(i):
	total = 0
	for k in range(i + 1):
		total = total + int(a[k])
	return total

def do(n):
	if n < 4:
		return summ(len(a) - 1)
	else:
		dp = {0: int(a[0]), 1: int(a[0]) + int(a[1]), 2: int(a[0]) + int(a[1]) + int(a[2])}
		k = 3
		while k < n:
			dp[k] = max(sums[k - 1] - dp[k - 1] + int(a[k]), sums[k - 2] - dp[k - 2] + int(a[k]) + int(a[k - 1]), sums[k - 3] - dp[k - 3] + int(a[k]) + int(a[k - 1]) + int(a[k - 2]))
			k += 1
		return dp[k - 1]
T = int(input())
for x in range(T):
	N = int(input())
	a = input().split(' ')
	a.reverse()
	sums = {}
	total = 0
	i = 0
	for b in a:
		total = total + int(b)
		sums[i] = total
		i += 1
	print(do(N))


T = int(input())
for i in range(T):
	N = int(input())
	bricks = list(map(int, input().split()))
	bricks.reverse()
	sums = [bricks[0]]
	for num in bricks[1:]:
		sums.append(sums[-1] + num)
	if N <= 3:
		print(sums[-1])
	else:
		dp = [sums[0], sums[1], sums[2]]
		dp = [bricks[0], bricks[0] + bricks[1], bricks[0] + bricks[1] + bricks[2]]
		for i in range(3, len(bricks)):
			one = sums[i - 1] - dp[i - 1] + bricks[i]
			two = sums[i - 2] - dp[i - 2] + bricks[i] + bricks[i - 1]
			three = sums[i - 3] - dp[i - 3] + bricks[i] + bricks[i - 1] + bricks[i - 2]
			dp.append(max(one, two, three))
		print(dp[-1])


def maxScore(a):
	dynmax = [(0, 0)] * (len(a) + 1)
	for i in range(1, min(4, len(a))):
		dynmax[i] = (sum(a[-i:]), 0)
	for i in range(4, len(a) + 1):
		for take in range(1, 4):
			(opp, mine) = dynmax[i - take]
			this = (sum(a[-i:-i + take]) + mine, opp)
			if this > dynmax[i]:
				dynmax[i] = this
	return dynmax[-1][0]
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(maxScore(a))


T = int(input())
S = []

def buildArrays(A, B, N):
	A[0] = S[N - 1]
	A[1] = S[N - 1] + S[N - 2]
	A[2] = S[N - 1] + S[N - 2] + S[N - 3]
	B[0] = 0
	B[1] = 0
	B[2] = 0
	for i in range(3, N):
		j = 1
		A[i] = S[N - 1 - i] + B[i - 1]
		t = S[N - 1 - i] + S[N - 1 - i + 1] + B[i - 2]
		if t > A[i]:
			A[i] = t
			j = 2
		t = S[N - 1 - i] + S[N - 1 - i + 1] + S[N - 1 - i + 2] + B[i - 3]
		if t > A[i]:
			A[i] = t
			j = 3
		B[i] = A[i - j]
for i in range(T):
	N = int(input())
	S = list(map(int, input().split()))
	A = [-1 for x in range(N)]
	B = [-1 for x in range(N)]
	buildArrays(A, B, N)
	print(A[N - 1])
	A.clear()
	B.clear()
	S.clear()


t = int(input())
for times in range(t):
	n = int(input())
	numbers = [int(num) for num in input().split()]
	numbers.reverse()
	sumnums = list(numbers)
	for i in range(1, n):
		sumnums[i] += sumnums[i - 1]
	memo = [-1] * (n + 1)
	memo[0] = numbers[0]
	memo[1] = numbers[1] + memo[0]
	memo[2] = numbers[2] + memo[1]
	for i in range(3, n):
		memo[i] = max(memo[i], sumnums[i - 1] - memo[i - 1] + numbers[i], sumnums[i - 2] - memo[i - 2] + numbers[i - 1] + numbers[i], sumnums[i - 3] - memo[i - 3] + numbers[i - 2] + numbers[i - 1] + numbers[i])
	print(memo[n - 1])


import sys
cases = int(sys.stdin.readline().strip())
for x in range(cases):
	sys.stdin.readline()
	bricks = [int(x) for x in sys.stdin.readline().split(' ')]
	n = len(bricks)
	values = {}
	totals = {}
	cur_total = None
	for position in reversed(range(n)):
		if position == n - 1:
			cur_total = bricks[position]
		else:
			cur_total += bricks[position]
		totals[position] = cur_total
		remaining = n - position
		if remaining <= 3:
			take = bricks[position:]
			for player in range(2):
				values[player, position] = sum(take)
		else:
			for player in range(2):
				max_result = float('-inf')
				for take_n in reversed(range(1, 4)):
					take = bricks[position:position + take_n]
					take_val = sum(take)
					other_player = 1 - player
					other_player_val = values[other_player, position + take_n]
					self_val = totals[position + take_n] - other_player_val
					result = take_val + self_val
					max_result = max(result, max_result)
				values[player, position] = max_result
	print(values[0, 0])


def f(A):
	A = A[::-1]
	s = [0] * len(A)
	s[0] = A[0]
	for i in range(1, len(A)):
		s[i] = s[i - 1] + A[i]
	dp = [0] * len(A)
	dp[0] = A[0]
	for i in range(1, min(len(A), 3)):
		dp[i] = dp[i - 1] + A[i]
	for i in range(3, len(A)):
		dp[i] = max(s[i - 1] - dp[i - 1], s[i - 2] - dp[i - 2] + A[i - 1], s[i - 3] - dp[i - 3] + A[i - 2] + A[i - 1]) + A[i]
	return dp[len(A) - 1]
for _ in range(int(input())):
	input()
	print(f([int(i) for i in input().split()]))


T = int(input())
for t in range(T):
	N = int(input())
	a = [0] + [int(c) for c in input().split(' ')][::-1]
	dp = [0] * (N + 1)
	s = [0] * (N + 1)
	for i in range(1, N + 1):
		s[i] = s[i - 1] + a[i]
	dp[0] = 0
	dp[1] = dp[0] + a[1]
	dp[2] = dp[1] + a[2]
	dp[3] = dp[2] + a[3]
	for i in range(4, N + 1):
		dp[i] = s[i - 1] - dp[i - 1] + a[i]
		dp[i] = max(dp[i], s[i - 2] - dp[i - 2] + a[i] + a[i - 1])
		dp[i] = max(dp[i], s[i - 3] - dp[i - 3] + a[i] + a[i - 1] + a[i - 2])
	print(dp[N])


for case in range(int(input())):
	N = int(input())
	bricks = [int(x) for x in input().split()]
	memo = [0] * N
	for i in range(1, 4):
		memo[-i] = (sum(bricks[-i:]), i)
	for i in range(4, len(memo) + 1):
		bestscore = 0
		bestmoves = None
		for j in range(1, 4):
			(_, hismoves) = memo[-i + j]
			score = sum(bricks[-i:-i + j])
			if j + hismoves < i:
				score += memo[-i + j + hismoves][0]
			if score >= bestscore:
				bestscore = score
				bestmoves = j
		memo[-i] = (bestscore, bestmoves)
	print(memo[0][0])


for case_t in range(int(input())):
	answer_list = [0]
	n = int(input())
	b = [int(item) for item in input().strip().split()]
	cur_sum = 0
	for i in range(1, n + 1):
		cur_sum += b[n - i]
		if i <= 3:
			answer_list.append(b[n - i] + answer_list[i - 1])
			continue
		maximus = cur_sum
		cur1 = maximus - answer_list[i - 1]
		cur2 = maximus - answer_list[i - 2]
		cur3 = maximus - answer_list[i - 3]
		answer_list.append(max(cur1, cur2, cur3))
	print(answer_list[-1])


def f(ar):
	res = []
	s = 0
	for i in range(3):
		s += ar[~i]
		res.append(s)
	for i in range(3, len(ar)):
		s += ar[~i]
		m = min(res)
		res[i % 3] = s - m
	return res[(len(ar) - 1) % 3]
for t in [1] * int(input()):
	input()
	ar = tuple(map(int, input().split()))
	print(f(ar))


import sys
from copy import deepcopy

def main():
	numCases = int(sys.stdin.readline())
	for caseIndex in range(0, numCases):
		gameLength = int(sys.stdin.readline())
		inputList = sys.stdin.readline().split()
		inputList = list(map(lambda x: int(x), inputList))
		suffixSum = deepcopy(inputList)
		for i in range(1, gameLength):
			suffixSum[gameLength - i - 1] = suffixSum[gameLength - i] + inputList[gameLength - i - 1]
		optimum = deepcopy(suffixSum)
		for i in range(4, gameLength + 1):
			choice1 = suffixSum[gameLength - i] - optimum[gameLength - i + 1]
			choice2 = suffixSum[gameLength - i] - optimum[gameLength - i + 2]
			choice3 = suffixSum[gameLength - i] - optimum[gameLength - i + 3]
			optimum[gameLength - i] = max(choice1, choice2, choice3)
		print(optimum[0])
main()


test_count = int(input())
for test_id in range(0, test_count):
	dummy = input()
	values = list(reversed(list(map(int, input().split()))))
	total = [0] * len(values)
	target = [-1] * len(values)
	for i in range(0, len(values)):
		best_index = -1
		max_value = -1
		for j in range(1, 4):
			current_total = sum(values[i - j + 1:i + 1])
			if i - j >= 0 and target[i - j] >= 0:
				current_total = current_total + total[target[i - j]]
			if current_total > max_value:
				max_value = current_total
				best_index = j
		total[i] = max_value
		target[i] = i - best_index
	print(total[-1])


def play_game(block_nums, size):
	block_nums.reverse()
	max_values = [0, block_nums[0], block_nums[0] + block_nums[1], block_nums[0] + block_nums[1] + block_nums[2]]
	best_picks = [0, 1, 2, 3]
	index = 3
	for i in range(3, size):
		cur_best = -99999999999
		cur_num = -9999999999
		cur_pick = 0
		for j in range(0, 3):
			cur_pick += block_nums[i - j]
			rival_val = max_values[i - j]
			cur_val = cur_pick + max_values[i - j - best_picks[i - j]]
			if cur_val - rival_val > cur_best:
				max_val = cur_val
				cur_best = cur_val - rival_val
				cur_num = j + 1
		max_values.append(max_val)
		best_picks.append(cur_num)
	print(max_values[-1])
testcases = int(input())
for i in range(0, testcases):
	num = int(input())
	array = input().split()
	array = [int(x) for x in array]
	play_game(array, num)


def max_play(cards):
	N = len(cards)
	sum_cards = [0] * N
	s = 0
	for i in range(N):
		s += cards[i]
		sum_cards[i] = s
	dp = [0] * N
	for i in [0, 1, 2]:
		dp[i] = sum(cards[0:i + 1])
	for i in range(3, N):
		dp[i] = max(cards[i] + sum_cards[i - 1] - dp[i - 1], cards[i] + cards[i - 1] + sum_cards[i - 2] - dp[i - 2], cards[i] + cards[i - 1] + cards[i - 2] + sum_cards[i - 3] - dp[i - 3])
	return dp[N - 1]
test_cases = int(input())
for t in range(test_cases):
	n = int(input())
	cards = [0] * n
	line = input().split()
	line.reverse()
	for i in range(n):
		cards[i] = int(line[i])
	print(max_play(cards))


def solve(A, n):
	A.reverse()
	if n <= 3:
		sum = 0
		for i in range(n):
			sum += A[i]
		return sum
	dp = list(range(n))
	sum = 0
	for i in range(3):
		sum += A[i]
		dp[i] = (sum, 0)
	for i in range(3, n):
		first = A[i]
		second = int()
		if first < A[i] + dp[i - 1][1]:
			first = A[i] + dp[i - 1][1]
			second = dp[i - 1][0]
		if first < A[i - 1] + A[i] + dp[i - 2][1]:
			first = A[i - 1] + A[i] + dp[i - 2][1]
			second = dp[i - 2][0]
		if first < A[i - 2] + A[i - 1] + A[i] + dp[i - 3][1]:
			first = A[i - 2] + A[i - 1] + A[i] + dp[i - 3][1]
			second = dp[i - 3][0]
		dp[i] = (first, second)
	return dp[n - 1][0]
T = int(input())
for t in range(T):
	n = int(input())
	A = input().split()
	for i in range(len(A)):
		A[i] = int(A[i])
	print(solve(A, n))


from itertools import accumulate

def solve():
	n = int(input())
	a = [int(i) for i in input().strip().split()]
	a.reverse()
	cumsum = list(accumulate(a))
	result = cumsum[:3]
	for i in range(3, n):
		result.append(cumsum[i] - min(result[i - 3:i]))
	return result[-1]
t = int(input())
for _ in range(t):
	print(solve())


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	arr = [int(x) for x in sys.stdin.readline().split()]
	arr.reverse()
	table = [0] * N
	table[0] = (arr[0], arr[0])
	table[1] = (sum(arr[:2]), sum(arr[:2]))
	table[2] = (sum(arr[:3]), sum(arr[:3]))
	s = sum(arr[:3])
	for i in range(3, N):
		s += arr[i]
		best = max(arr[i] + table[i - 1][1] - table[i - 1][0], arr[i] + arr[i - 1] + table[i - 2][1] - table[i - 2][0], arr[i] + arr[i - 1] + arr[i - 2] + table[i - 3][1] - table[i - 3][0])
		table[i] = (best, s)
	print(table[-1][0])


def getMax(bricks, N):
	if N == 0:
		return 0
	if N <= 3:
		return sum(bricks)
	scores = [0]
	total = 0
	for i in range(1, 4):
		total += bricks[-i]
		scores.append(total)
	for i in range(4, N + 1):
		total += bricks[-i]
		choice_1 = total - scores[i - 1]
		choice_2 = total - scores[i - 2]
		choice_3 = total - scores[i - 3]
		maxScore = max(choice_1, choice_2, choice_3)
		scores.append(maxScore)
	print(scores[-1])
T = int(input())
for i in range(T):
	N = int(input())
	bricks = [int(x) for x in input().split()]
	getMax(bricks, N)


numinputs = int(input())
for dummy in range(numinputs):
	n = int(input())
	scores = [int(val) for val in input().split()]
	dp = [0] * n
	sumdp = [0] * n
	dp[n - 1] = scores[n - 1]
	sumdp[n - 1] = scores[n - 1]
	dp[n - 2] = scores[n - 2] + scores[n - 1]
	sumdp[n - 2] = scores[n - 2] + scores[n - 1]
	dp[n - 3] = scores[n - 3] + scores[n - 2] + scores[n - 1]
	sumdp[n - 3] = scores[n - 2] + scores[n - 1] + scores[n - 3]
	for i in range(n - 4, -1, -1):
		sumdp[i] = sumdp[i + 1] + scores[i]
		dp[i] = max(sumdp[i + 1] - dp[i + 1] + scores[i], sumdp[i + 2] - dp[i + 2] + scores[i] + scores[i + 1], sumdp[i + 3] - dp[i + 3] + scores[i] + scores[i + 1] + scores[i + 2])
	print(dp[0])


case_count = int(input())
cases = []
for i in range(case_count):
	_ = input()
	cases.append([int(i) for i in input().split()])
for case in cases:
	size = len(case)
	table = [[0 for _ in range(size + 3)] for _ in range(2)]
	gain = case[:]
	gain.append(0)
	gain.append(0)
	gain.append(0)
	for i in range(len(case) - 1, -1, -1):
		table[0][i] = max(gain[i] + table[1][i + 1], gain[i] + gain[i + 1] + table[1][i + 2], gain[i] + gain[i + 1] + gain[i + 2] + table[1][i + 3])
		table[1][i] = min(table[0][i + 1], table[0][i + 2], table[0][i + 3])
	print(str(table[0][0]))


def cal(a, n):
	ar = [a[n - 1], a[n - 1] + a[n - 2], a[n - 1] + a[n - 2] + a[n - 3]]
	su = [a[n - 1]]
	for i in range(1, n):
		su.append(su[i - 1] + a[n - i - 1])
	for i in range(3, n):
		ar.append(max(a[n - 1 - i] + (su[i - 1] - ar[i - 1]), a[n - i - 1] + a[n - i] + (su[i - 2] - ar[i - 2]), a[n - i - 1] + a[n - i] + a[n - i + 1] + (su[i - 3] - ar[i - 3])))
	return ar[n - 1]
t = int(input())
a = []
b = []
for i in range(t):
	b.append(int(input()))
	a.append([])
	for k in input().split():
		a[i].append(int(k))
for k in range(t):
	print(cal(a[k], b[k]))


def max_score(bricks):
	scores = [0 for _ in range(len(bricks))]
	scores[0] = bricks[0]
	scores[1] = scores[0] + bricks[1]
	scores[2] = scores[1] + bricks[2]
	psum = [0 for _ in range(len(bricks))]
	psum[0] = bricks[0]
	for i in range(1, len(psum)):
		psum[i] = psum[i - 1] + bricks[i]
	for i in range(3, len(bricks)):
		scores[i] = max((psum[i - 1] - scores[i - 1] + bricks[i], psum[i - 2] - scores[i - 2] + bricks[i] + bricks[i - 1], psum[i - 3] - scores[i - 3] + bricks[i] + bricks[i - 1] + bricks[i - 2]))
	return scores[-1]
t = int(input())
for _ in range(t):
	input()
	bricks = [int(el) for el in input().split()]
	print(max_score(list(reversed(bricks))))


def f(bricks, n):
	dp = [0 for _ in range(n + 3)]
	sums = [0 for _ in range(n + 3)]
	for i in range(n - 1, -1, -1):
		sums[i] = sums[i + 1] + bricks[i]
	for i in range(n - 1, -1, -1):
		dp[i] = max(bricks[i] - dp[i + 1] + sums[i + 1], bricks[i] + bricks[i + 1] - dp[i + 2] + sums[i + 2], bricks[i] + bricks[i + 1] + bricks[i + 2] - dp[i + 3] + sums[i + 3])
	return dp[0]
t = int(input())
for _ in range(t):
	n = int(input())
	bricks = [int(v) for v in input().split()]
	bricks += [0, 0, 0]
	print(f(bricks, n))


def play_game(array, N):
	dp = [0 for _ in range(N + 7)]
	if N <= 3:
		return sum(array)
	for _ in range(3):
		array.append(0)
	for i in range(N)[::-1]:
		dp[i] = max(array[i] + min(dp[i + 2], dp[i + 3], dp[i + 4]), array[i] + array[i + 1] + min(dp[i + 3], dp[i + 4], dp[i + 5]), array[i] + array[i + 1] + array[i + 2] + min(dp[i + 4], dp[i + 5], dp[i + 6]))
	return dp[0]
T = int(input())
for _ in range(T):
	N = int(input())
	stk = [int(x) for x in input().split()]
	print(play_game(stk, N))


from itertools import accumulate

def main():
	ncases = int(input())
	for _ in range(ncases):
		length = int(input())
		bricks = [int(f) for f in reversed(input().split())]
		assert len(bricks) == length
		cumsum = [0] + list(accumulate(bricks))
		score = [0]
		for i in range(1, length + 1):
			best = 0
			for take in range(1, min(3, i) + 1):
				best = max(best, sum(bricks[i - take:i]) + cumsum[i - take] - score[i - take])
			score.append(best)
		print(score[-1])
main()


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().strip().split()]

	def calc(arr):
		alen = len(arr)
		if alen < 4:
			return sum(arr)
		presum = [0] * alen
		presum[0] = arr[0]
		for i in range(1, alen):
			presum[i] = presum[i - 1] + arr[i]
		dp = [0] * alen
		dp[0] = arr[0]
		dp[1] = arr[1] + dp[0]
		dp[2] = arr[2] + dp[1]
		for i in range(3, alen):
			x = arr[i] + presum[i - 1] - dp[i - 1]
			y = presum[i - 2] + arr[i] + arr[i - 1] - dp[i - 2]
			z = presum[i - 3] + arr[i] + arr[i - 1] + arr[i - 2] - dp[i - 3]
			dp[i] = max(x, y, z)
		return dp[alen - 1]
	arr.reverse()
	print(calc(arr))


def iterative():
	for T in range(int(input())):
		n = int(input())
		A = [int(x) for x in input().split()]
		A.reverse()
		Sum = [A[0]]
		for i in range(1, n):
			Sum.append(Sum[i - 1] + A[i])
		dp = [A[0], A[0] + A[1], A[0] + A[1] + A[2]]
		for i in range(3, n):
			dp.append(max(A[i] + (Sum[i - 1] - dp[i - 1]), A[i] + A[i - 1] + (Sum[i - 2] - dp[i - 2]), A[i] + A[i - 1] + A[i - 2] + (Sum[i - 3] - dp[i - 3])))
		print(dp[-1])
iterative()


T = int(input())
for case in range(T):
	N = int(input())
	arr = list(map(int, input().rstrip().split(' ')))
	dp = [0] * len(arr)
	dp[len(arr) - 1] = arr[len(arr) - 1]
	dp[len(arr) - 2] = arr[len(arr) - 2] + dp[len(arr) - 1]
	dp[len(arr) - 3] = arr[len(arr) - 3] + dp[len(arr) - 2]
	for i in range(len(arr) - 4, -1, -1):
		dp[i] = max(arr[i] - dp[i + 1], sum(arr[i:i + 2]) - dp[i + 2], sum(arr[i:i + 3]) - dp[i + 3])
	net_win = dp[0]
	print((net_win + sum(arr)) // 2)


for _ in range(int(input())):
	n = int(input())
	a = map(int, input().split())
	a = list(a)
	a.reverse()
	if n <= 3:
		print(sum(a))
	else:
		f = [0 for i in range(n)]
		(f[0], f[1], f[2]) = (a[0], a[0] + a[1], a[0] + a[1] + a[2])
		su = f[2]
		for i in range(3, n):
			su += a[i]
			f[i] = su - min([f[i - 1], f[i - 2], f[i - 3]])
		print(f[n - 1])


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().strip().split()]

	def calc(arr):
		alen = len(arr)
		if alen < 4:
			return sum(arr)
		presum = [0] * alen
		presum[0] = arr[0]
		for i in range(1, alen):
			presum[i] = presum[i - 1] + arr[i]
		dp = [0] * alen
		dp[0] = arr[0]
		dp[1] = arr[1] + dp[0]
		dp[2] = arr[2] + dp[1]
		for i in range(3, alen):
			x = arr[i] + presum[i - 1] - dp[i - 1]
			y = presum[i - 2] + arr[i] + arr[i - 1] - dp[i - 2]
			z = presum[i - 3] + arr[i] + arr[i - 1] + arr[i - 2] - dp[i - 3]
			dp[i] = max(x, y, z)
		return dp[alen - 1]
	arr.reverse()
	print(calc(arr))


cases = int(input())
for _ in range(cases):
	size = int(input())
	B = [int(x) for x in input().split()]

	def score(k, memo={}):
		if k in memo:
			return memo[k]
		res = 0
		if size - k <= 3:
			res = sum(B[k:])
		else:
			res = max(B[k] + min(score(k + 2), score(k + 3), score(k + 4)), B[k] + B[k + 1] + min(score(k + 3), score(k + 4), score(k + 5)), B[k] + B[k + 1] + B[k + 2] + min(score(k + 4), score(k + 5), score(k + 6)))
		memo[k] = res
		return res
	for k in reversed(range(size)):
		score(k)
	print(score(0))


def solution(nums):
	score = [0 for i in range(len(nums))]
	pick = [0 for i in range(len(nums))]
	score[-1] = nums[-1]
	score[-2] = nums[-2] + score[-1]
	score[-3] = nums[-3] + score[-2]
	pick[-1] = 1
	pick[-2] = 2
	pick[-3] = 3
	for i in range(len(nums) - 4, -1, -1):
		if i + pick[i + 1] + 1 >= len(nums):
			pick1 = nums[i]
		else:
			pick1 = nums[i] + score[i + pick[i + 1] + 1]
		if i + 1 + pick[i + 2] + 1 >= len(nums):
			pick2 = nums[i] + nums[i + 1]
		else:
			pick2 = nums[i] + nums[i + 1] + score[i + 1 + pick[i + 2] + 1]
		if i + 2 + pick[i + 3] + 1 >= len(nums):
			pick3 = nums[i] + nums[i + 1] + nums[i + 2]
		else:
			pick3 = nums[i] + nums[i + 1] + nums[i + 2] + score[i + 2 + pick[i + 3] + 1]
		if pick1 > pick2:
			score[i] = pick1
			pick[i] = 1
		else:
			score[i] = pick2
			pick[i] = 2
		if pick3 > score[i]:
			score[i] = pick3
			pick[i] = 3
	return score[0]
numsOfInput = int(input())
for i in range(numsOfInput):
	n = int(input())
	nums = list(map(int, input().split()))
	print(solution(nums))


def inv(x):
	return abs(x - 1)
t = int(input())
for _ in range(t):
	n = int(input())
	lis = list(map(int, input().split()))
	T = [[[0, 0], [0, 0]] for _ in range(n + 3)]
	for (i, x) in reversed(list(enumerate(lis))):
		for j in range(2):
			for d in range(1, 4):
				if T[i + d][inv(j)][j] + sum(lis[i:i + d]) > T[i][j][j]:
					T[i][j][j] = T[i + d][inv(j)][j] + sum(lis[i:i + d])
					T[i][j][inv(j)] = T[i + d][inv(j)][inv(j)]
	print(T[0][0][0])


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().strip().split()]

	def calc(arr):
		alen = len(arr)
		if alen < 4:
			return sum(arr)
		presum = [0] * alen
		presum[0] = arr[0]
		for i in range(1, alen):
			presum[i] = presum[i - 1] + arr[i]
		dp = [0] * alen
		dp[0] = arr[0]
		dp[1] = arr[1] + dp[0]
		dp[2] = arr[2] + dp[1]
		for i in range(3, alen):
			x = arr[i] + presum[i - 1] - dp[i - 1]
			y = presum[i - 2] + arr[i] + arr[i - 1] - dp[i - 2]
			z = presum[i - 3] + arr[i] + arr[i - 1] + arr[i - 2] - dp[i - 3]
			dp[i] = max(x, y, z)
		return dp[alen - 1]
	arr.reverse()
	print(calc(arr))


T = int(input())
for i in range(0, T):
	N = int(input())
	sum = [0] * (N + 1)
	d = [0] * N
	brick = list(map(int, input().split()))
	for j in range(N - 1, -1, -1):
		sum[j] = sum[j + 1] + brick[j]
	d[N - 1] = brick[N - 1]
	d[N - 2] = d[N - 1] + brick[N - 2]
	d[N - 3] = d[N - 2] + brick[N - 3]
	for j in range(N - 4, -1, -1):
		d[j] = max(sum[j + 1] - d[j + 1] + brick[j], sum[j + 2] - d[j + 2] + brick[j] + brick[j + 1], sum[j + 3] - d[j + 3] + brick[j] + brick[j + 1] + brick[j + 2])
	print(d[0])


t = eval(input())

def max(a, b, c):
	result = a
	if result < b:
		result = b
	if result < c:
		result = c
	return result
while t > 0:
	t -= 1
	n = eval(input())
	arr = list(map(int, input().split()))
	sumRight = [0] * (n + 1)
	sumRight[n] = 0
	for i in reversed(range(n)):
		sumRight[i] = arr[i] + sumRight[i + 1]
	best = [0] * (n + 1)
	best[n] = 0
	for i in reversed(range(n)):
		temp1 = arr[i] + sumRight[i + 1] - best[i + 1]
		temp2 = 0
		temp3 = 0
		if i <= n - 2:
			temp2 = arr[i] + arr[i + 1] + sumRight[i + 2] - best[i + 2]
		if i <= n - 3:
			temp3 = arr[i] + arr[i + 1] + arr[i + 2] + sumRight[i + 3] - best[i + 3]
		best[i] = max(temp1, temp2, temp3)
	print(best[0])


import sys
T = int(sys.stdin.readline())
for case in range(T):
	N = int(sys.stdin.readline())
	bs = [int(X) for X in sys.stdin.readline().split()]
	bs.reverse()
	scores = [(sum(bs[:i]), 0) for i in [1, 2, 3]]
	for i in range(3, N):
		score_take_1 = (bs[i] + scores[i - 1][1], scores[i - 1][0])
		score_take_2 = (bs[i] + bs[i - 1] + scores[i - 2][1], scores[i - 2][0])
		score_take_3 = (bs[i] + bs[i - 1] + bs[i - 2] + scores[i - 3][1], scores[i - 3][0])
		scores.append(max(score_take_1, score_take_2, score_take_3))
	print(scores[-1][0])


t = int(input())

def run():
	n = int(input())
	nums = [0, 0] + list(reversed(list(map(int, input().strip().split(' ')))))
	state = [(0, 0)] * (n + 2)
	for i in range(2, n + 2):
		one = nums[i] + state[i - 1 - state[i - 1][1]][0]
		two = nums[i] + nums[i - 1] + state[i - 2 - state[i - 2][1]][0]
		three = nums[i] + nums[i - 1] + nums[i - 2] + state[i - 3 - state[i - 3][1]][0]
		state[i] = max((one, 1), (two, 2), (three, 3))
	print(state[-1][0])
for i in range(t):
	run()


readinput = lambda x: [int(y) for y in x.split()]

def solve(array):
	array = array[::-1]
	scores = [0 for _ in range(len(array))]
	total = 0
	for i in range(3):
		total += array[i]
		scores[i] = total
	for i in range(3, len(array)):
		total += array[i]
		min_move = min(scores[i - 1], min(scores[i - 2], scores[i - 3]))
		scores[i] = total - min_move
	return scores[-1]
for testcase in range(int(input())):
	N = readinput(input())
	array = readinput(input())
	print(solve(array))


def bricks_game(N, A):
	P = [0 for _ in range(N)]
	P[0] = A[0]
	for i in range(1, N):
		P[i] += P[i - 1] + A[i]
	D = [0 for _ in range(N)]
	D[0] = A[0]
	D[1] = D[0] + A[1]
	D[2] = D[1] + A[2]
	for i in range(3, N):
		X = P[i - 1] + A[i] - D[i - 1]
		Y = P[i - 2] + A[i] + A[i - 1] - D[i - 2]
		Z = P[i - 3] + A[i] + A[i - 1] + A[i - 2] - D[i - 3]
		D[i] = max(X, Y, Z)
	return D[-1]

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = [int(i) for i in input().split()]
		print(bricks_game(N, A[::-1]))
main()


t = int(input())
for t in range(0, t):
	n = int(input())
	arr = input().split()
	arr.reverse()
	sumarr = []
	for i in range(0, n):
		arr[i] = int(arr[i])
		if i >= 1:
			sumarr.append(sumarr[i - 1] + arr[i])
		else:
			sumarr.append(arr[0])
	dp = []
	dp.append(sumarr[0])
	dp.append(sumarr[1])
	dp.append(sumarr[2])
	for i in range(3, n):
		val = max(sumarr[i - 1] - dp[i - 1] + arr[i], sumarr[i - 2] - dp[i - 2] + arr[i - 1] + arr[i], sumarr[i - 3] - dp[i - 3] + arr[i - 1] + arr[i - 2] + arr[i])
		dp.append(val)
	print(dp[n - 1])


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().strip().split()]

	def calc(arr):
		alen = len(arr)
		if alen < 4:
			return sum(arr)
		presum = [0] * alen
		presum[0] = arr[0]
		for i in range(1, alen):
			presum[i] = presum[i - 1] + arr[i]
		dp = [0] * alen
		dp[0] = arr[0]
		dp[1] = arr[1] + dp[0]
		dp[2] = arr[2] + dp[1]
		for i in range(3, alen):
			x = arr[i] + presum[i - 1] - dp[i - 1]
			y = presum[i - 2] + arr[i] + arr[i - 1] - dp[i - 2]
			z = presum[i - 3] + arr[i] + arr[i - 1] + arr[i - 2] - dp[i - 3]
			dp[i] = max(x, y, z)
		return dp[alen - 1]
	arr.reverse()
	print(calc(arr))


for _ in range(int(input())):
	n = int(input())
	bricks = list(map(int, input().strip().split(' ')))
	bricks.reverse()
	sums = []
	sums.append(bricks[0])
	dp = []
	for i in range(1, len(bricks)):
		sums.append(bricks[i] + sums[i - 1])
	dp = [0] * len(bricks)
	dp[0] = bricks[0]
	dp[1] = dp[0] + bricks[1]
	dp[2] = dp[1] + bricks[2]
	for i in range(3, len(bricks)):
		dp[i] = max(-1, sums[i - 1] - dp[i - 1] + bricks[i])
		dp[i] = max(dp[i], sums[i - 2] - dp[i - 2] + bricks[i] + bricks[i - 1])
		dp[i] = max(dp[i], sums[i - 3] - dp[i - 3] + bricks[i] + bricks[i - 1] + bricks[i - 2])
	print(dp[len(bricks) - 1])


def score(V):
	if len(V) <= 3:
		return sum(V)
	F = [0] * N
	F[0] = V[0]
	for i in range(1, 3):
		F[i] = F[i - 1] + V[i]
	for j in range(3, len(V)):
		m = 0
		c = [0] * 3
		for k in range(3):
			m += V[j - k]
			hi = j - k - 1 if j - k - 1 >= 0 else 0
			lo = j - k - 4 if j - k - 4 >= 0 else 0
			t = F[lo:hi]
			if len(t) < 3:
				t.append(0)
			o = min(t) if t else 0
			c[k] = m + o
		F[j] = max(c)
	return F[-1]
T = int(input())
for t in range(T):
	N = int(input())
	V = list(map(int, input().split()))
	V.reverse()
	print(score(V))


def brick_game(B):
	B.reverse()
	Sum_B = [B[0]]
	for x in B[1:]:
		Sum_B.append(Sum_B[-1] + x)
	dp = [0 for _ in range(len(B))]
	(dp[0], dp[1], dp[2]) = (Sum_B[0], Sum_B[1], Sum_B[2])
	for i in range(3, len(B)):
		dp[i] = Sum_B[i] - dp[i - 1]
		dp[i] = max(dp[i], Sum_B[i] - dp[i - 2])
		dp[i] = max(dp[i], Sum_B[i] - dp[i - 3])
	return dp[-1]
T = int(input())
for _ in range(T):
	input()
	B = list(map(int, input().split()))
	print(brick_game(B))


t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	dp = [0] * n
	dp[n - 1] = b[n - 1]
	dp[n - 2] = dp[n - 1] + b[n - 2]
	dp[n - 3] = dp[n - 2] + b[n - 3]
	s = dp[:]
	for i in range(n - 4, -1, -1):
		a1 = b[i] + s[i + 1] - dp[i + 1]
		a2 = b[i] + b[i + 1] + s[i + 2] - dp[i + 2]
		a3 = b[i] + b[i + 1] + b[i + 2] + s[i + 3] - dp[i + 3]
		dp[i] = max(a1, a2, a3)
		s[i] = s[i + 1] + b[i]
	print(dp[0])


def main():
	t = input()
	t = int(t)
	for i in range(t):
		n = input()
		n = int(n)
		lis = list(map(int, input().split()))
		dp = [0] * (n + 10)
		sumi = 0
		for i in range(n - 1, -1, -1):
			sumi += lis[i]
			dp[i] = sumi - min(min(dp[i + 1], dp[i + 2]), dp[i + 3])
		print(dp[0])
main()


cache = [-1 for x in range(0, 10001)]
count = 0
ar = []

def maxSum(x, i):
	sum1 = 0
	if x == 0:
		sum1 = ar[i]
	elif x == 1:
		sum1 = ar[i] + ar[i + 1]
	elif x == 2:
		sum1 = ar[i] + ar[i + 1] + ar[i + 2]
	elif cache[i] < 0:
		totSum = 0
		for j in range(i, len(ar)):
			totSum += ar[j]
		sum1 = max(totSum - maxSum(x - 1, i + 1), totSum - maxSum(x - 2, i + 2), totSum - maxSum(x - 3, i + 3))
		cache[i] = sum1
	else:
		sum1 = cache[i]
	return sum1

def findSum(N):
	sum1 = 0
	for i in range(0, N):
		sum1 += ar[i]
		if i == 0:
			cache[i] = ar[i]
		elif i == 1:
			cache[i] = ar[i] + ar[i - 1]
		elif i == 2:
			cache[i] = ar[i] + ar[i - 1] + ar[i - 2]
		else:
			cache[i] = sum1 - min(cache[i - 1], cache[i - 2], cache[i - 3])
	return cache[N - 1]
T = int(input())
for j in range(0, T):
	N = int(input())
	cache = [-1 for x in range(0, N)]
	ar = [int(n) for n in input().split()]
	ar.reverse()
	print(findSum(N))


def main():
	t = int(input())
	while t:
		n = int(input())
		a = input().split()
		value = [0] * n
		for i in range(0, n):
			value[i] = int(a[n - 1 - i])
		oppo = [0] * n
		plyr = [0] * n
		plyr[0] = value[0]
		plyr[1] = value[0] + value[1]
		plyr[2] = value[0] + value[1] + value[2]
		cur_total = value[0] + value[1] + value[2]
		for i in range(3, n):
			plyr[i] = max(value[i] + oppo[i - 1], value[i] + value[i - 1] + oppo[i - 2], value[i] + value[i - 1] + value[i - 2] + oppo[i - 3])
			cur_total += value[i]
			oppo[i] = cur_total - plyr[i]
		print(plyr[n - 1])
		t -= 1
main()


import sys
T = int(input())
for t in range(0, T):
	n = int(input())
	a = list(map(int, input().split()))
	a.reverse()
	s = [0] * n
	for i in range(0, n):
		s[i] = a[i] + s[i - 1]
	b = [0] * n
	b[0] = a[0]
	b[1] = a[0] + a[1]
	b[2] = a[0] + a[1] + a[2]
	for i in range(3, n):
		b[i] = max(a[i] + s[i - 1] - b[i - 1], a[i] + a[i - 1] + s[i - 2] - b[i - 2], a[i] + a[i - 1] + a[i - 2] + s[i - 3] - b[i - 3])
	print(b[n - 1])


from itertools import accumulate
for _ in range(int(input())):
	n = int(input())
	br = [int(x) for x in input().split()]
	br.reverse()
	dp = [0] * n
	sums = list(accumulate(br))
	dp[0] = sums[0]
	dp[1] = sums[1]
	dp[2] = sums[2]
	for i in range(3, n):
		dp[i] = max(sums[i] - dp[i - 1], sums[i] - dp[i - 2], sums[i] - dp[i - 3])
	print(dp[n - 1])


def solve(ns):
	N = len(ns)
	sums = [0 for _ in ns] + [0]
	for i in range(N):
		sums[i + 1] = sums[i] + ns[i]
	m = {0: 0}
	for i in range(N + 1):
		if i >= 3:
			one = ns[i - 1] + sums[i - 1] - m[i - 1]
			two = ns[i - 1] + ns[i - 2] + sums[i - 2] - m[i - 2]
			thr = ns[i - 1] + ns[i - 2] + ns[i - 3] + sums[i - 3] - m[i - 3]
			m[i] = max(one, two, thr)
		else:
			m[i] = sums[i]
	return m[N]
for _ in range(int(input())):
	ns = [int(w) for w in [input(), input()][1].split()]
	print(solve(list(reversed(ns))))


def max_score(bricks):
	sz = len(bricks)
	max_score_from = [0] * sz
	max_score_from[-1] = bricks[-1]
	max_score_from[-2] = max_score_from[-1] + bricks[-2]
	max_score_from[-3] = max_score_from[-2] + bricks[-3]
	backward_sum = max_score_from[:]
	for i in range(sz - 4, -1, -1):
		score_take_one = bricks[i] + backward_sum[i + 1] - max_score_from[i + 1]
		score_take_two = bricks[i] + bricks[i + 1] + backward_sum[i + 2] - max_score_from[i + 2]
		score_take_three = bricks[i] + bricks[i + 1] + bricks[i + 2] + backward_sum[i + 3] - max_score_from[i + 3]
		max_score_from[i] = max(score_take_one, score_take_two, score_take_three)
		backward_sum[i] = backward_sum[i + 1] + bricks[i]
	return max_score_from[0]
test_case_num = int(input())
for _ in range(test_case_num):
	input()
	bricks = list(map(int, input().split()))
	print(max_score(bricks))


for i in range(int(input())):
	input()
	li = list(reversed([int(x) for x in input().split()]))
	su = [li[0]]
	for i in range(1, len(li)):
		su.append(su[i - 1] + li[i])
	dp = [0 for i in range(len(li) + 1)]
	dp[0] = su[0]
	dp[1] = su[1]
	dp[2] = su[2]
	for k in range(3, len(li)):
		dp[k] = max(li[k] + (su[k - 1] - dp[k - 1]), li[k] + li[k - 1] + li[k - 2] + (su[k - 3] - dp[k - 3]), li[k] + li[k - 1] + (su[k - 2] - dp[k - 2]))
	print(dp[len(li) - 1])


testCases = int(input())
for testCase in range(testCases):
	n = int(input())
	stack = list(map(int, input().split()))
	s = [0 for i in range(n + 1)]
	currSum = 0
	for i in range(1, n + 1):
		currSum += stack[-i]
		if i <= 3:
			s[i] = currSum
		else:
			c1 = currSum - s[i - 1]
			c2 = currSum - s[i - 2]
			c3 = currSum - s[i - 3]
			s[i] = max(c1, c2, c3)
	print(s[n])


import sys

def max_profit(arr):
	max_ahead = list(arr)
	max_move = list(arr)
	L = len(arr)
	max_move[L - 1] = 1
	max_move[L - 2] = 2
	max_move[L - 3] = 3
	max_ahead[L - 2] = max_ahead[L - 2] + max_ahead[L - 1]
	max_ahead[L - 3] = max_ahead[L - 3] + max_ahead[L - 2]
	max_ahead.insert(L, 0)
	for (i, val) in enumerate(reversed(max_ahead)):
		pos = L - i
		if pos < L - 3:
			p = arr[pos] + max_ahead[pos + 1 + max_move[pos + 1]]
			q = arr[pos] + arr[pos + 1] + max_ahead[pos + 2 + max_move[pos + 2]]
			r = arr[pos] + arr[pos + 1] + arr[pos + 2] + max_ahead[pos + 3 + max_move[pos + 3]]
			max_ahead[pos] = max(p, q, r)
			if max_ahead[pos] == p:
				max_move[pos] = 1
			if max_ahead[pos] == q:
				max_move[pos] = 2
			if max_ahead[pos] == r:
				max_move[pos] = 3
	return max_ahead[0]
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
	print(max_profit(arr))


import operator

def f(ms1, ms2, a1, a2, i, s):
	A = s[i] + ms1[i + 1 + a2[i + 1]]
	B = s[i] + s[i + 1] + ms1[i + 2 + a2[i + 2]]
	C = s[i] + s[i + 1] + s[i + 2] + ms1[i + 3 + a2[i + 3]]
	L = [(A, 1), (B, 2), (C, 3)]
	return sorted(L, key=operator.itemgetter(0), reverse=True)[0]
for _ in range(int(input())):
	n = int(input())
	s = [int(x) for x in input().split()]
	if n < 4:
		print(sum(s))
		continue
	ms1 = [0] * (n + 1)
	a1 = [0] * (n + 1)
	ms2 = [0] * (n + 1)
	a2 = [0] * (n + 1)
	for i in range(n - 3, n):
		ms1[i] = sum(s[i:])
		a1[i] = n - i
		ms2[i] = sum(s[i:])
		a2[i] = n - i
	for i in range(n - 4, -1, -1):
		(ms1[i], a1[i]) = f(ms1, ms2, a1, a2, i, s)
		(ms2[i], a2[i]) = f(ms2, ms1, a2, a1, i, s)
	print(ms1[0])


from collections import defaultdict
for tc in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	memo = defaultdict(int)
	key = defaultdict(int)
	(memo[n - 1], key[n - 1]) = (li[n - 1], 1)
	(memo[n - 2], key[n - 2]) = (li[n - 2] + memo[n - 1], 2)
	(memo[n - 3], key[n - 3]) = (li[n - 3] + memo[n - 2], 3)
	for i in range(n - 3):
		k = n - 4 - i
		l2 = []
		for j in range(3):
			a = 0
			for s in range(j + 1):
				a += li[k + s]
			t = k + j + 1 + key[k + j + 1]
			a += memo[t]
			l2 += ((a, j + 1),)
		l2.sort()
		memo[k] = l2[-1][0]
		key[k] = l2[-1][1]
	print(memo[0])


def maxScore(n, seq):
	prefixSum = [seq[0], seq[0] + seq[1], seq[0] + seq[1] + seq[2]]
	table = [seq[0], seq[0] + seq[1], seq[0] + seq[1] + seq[2]]
	if n < 4:
		return table[-1]
	for i in range(3, n):
		prefixSum.append(prefixSum[-1] + seq[i])
		best = 0
		for x in (0, 1, 2):
			a = sum(seq[i - x:i + 1])
			b = prefixSum[i - x - 1]
			c = table[i - x - 1]
			best = max(a + b - c, best)
			pass
		table.append(best)
		pass
	return table[-1]
t = int(input())
for i in range(t):
	n = int(input())
	seq = list(map(int, input().split()))
	seq.reverse()
	print(maxScore(n, seq))
	pass


def maxScore(B, n):
	Mx = [0] * n
	Mx[-1] = B[-1]
	Mx[-2] = sum(B[-2:])
	Mx[-3] = sum(B[-3:])
	BackSum = Mx[:]
	for i in range(n - 4, -1, -1):
		x1 = B[i] + BackSum[i + 1] - Mx[i + 1]
		x2 = B[i] + B[i + 1] + BackSum[i + 2] - Mx[i + 2]
		x3 = B[i] + B[i + 1] + B[i + 2] + BackSum[i + 3] - Mx[i + 3]
		Mx[i] = max(x1, x2, x3)
		BackSum[i] = B[i] + BackSum[i + 1]
	return Mx[0]
for _ in range(int(input())):
	n = int(input())
	Bricks = [int(i) for i in input().strip().split()]
	if n < 4:
		print(sum(Bricks))
	else:
		print(maxScore(Bricks, n))


INF = 10 ** 18

def one_test():
	n = int(input())
	a = list(reversed(list(map(int, input().split()))))
	dp = [0] * (n + 1)
	for i in range(n):
		take = 0
		dp[i + 1] = -INF
		for j in range(i, max(i - 3, -1), -1):
			take += a[j]
			dp[i + 1] = max(dp[i + 1], take - dp[j])
	return (sum(a) + dp[n]) // 2
t = int(input())
for i in range(t):
	print(one_test())


T = int(input().strip())
for t in range(T):
	n = int(input().strip())
	A = list(map(int, input().strip().split(' ')))
	A.reverse()
	S = [0]
	for t in range(1, n + 1):
		S.append(S[t - 1] + A[t - 1])
	F = [0 for t in range(n)]
	F[0:3] = S[1:4]
	for t in range(3, n):
		temp1 = A[t] + S[t] - F[t - 1]
		temp2 = A[t - 1] + A[t] + S[t - 1] - F[t - 2]
		temp3 = A[t - 2] + A[t - 1] + A[t] + S[t - 2] - F[t - 3]
		F[t] = max(temp1, temp2, temp3)
	print(F[n - 1])


def solve(A):
	dp = [0] * (len(A) + 3)
	A2 = A + [0, 0, 0]
	for i in range(len(A) - 1, -1, -1):
		dp[i] = max(A2[i] - dp[i + 1], A2[i] + A2[i + 1] - dp[i + 2], A2[i] + A2[i + 1] + A2[i + 2] - dp[i + 3])
	return (dp[0] + sum(A)) // 2
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().strip().split()]
	print(solve(A))


T = int(input())
for T_i in range(T):
	n = int(input())
	l = [int(x) for x in input().split()]
	l.reverse()
	best = [0 for x in range(n)]
	p = []
	p.append(l[0])
	for i in range(1, n):
		p.append(p[i - 1] + l[i])
	best[0] = l[0]
	best[1] = best[0] + l[1]
	best[2] = best[1] + l[2]
	for i in range(3, n):
		best[i] = max(-1, p[i - 1] - best[i - 1] + l[i])
		best[i] = max(best[i], p[i - 2] - best[i - 2] + l[i] + l[i - 1])
		best[i] = max(best[i], p[i - 3] - best[i - 3] + l[i] + l[i - 1] + l[i - 2])
	print(best[n - 1])


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = list(reversed(l))
	q = [0 for i in l]
	m = [0 for i in l]
	for i in range(len(l)):
		if i <= 2:
			if i == 0:
				q[i] = l[i]
				m[i] = q[i]
			else:
				q[i] = l[i] + q[i - 1]
				m[i] = q[i]
		else:
			a = l[i] + q[i - 1] - m[i - 1]
			b = l[i] + l[i - 1] + q[i - 2] - m[i - 2]
			c = l[i] + l[i - 1] + l[i - 2] + q[i - 3] - m[i - 3]
			m[i] = max(a, b, c)
			q[i] = l[i] + q[i - 1]
	print(m[-1])


def get_memo(n, memo):
	if n >= len(memo):
		return 0
	else:
		return memo[n]

def solver(N, bStack):
	memo = [0] * N
	for n in range(N - 1, -1, -1):
		if n == N - 1:
			memo[n] = bStack[n]
		elif n == N - 2:
			memo[n] = sum(bStack[n:])
		elif n == N - 3:
			memo[n] = sum(bStack[n:])
		else:
			x = bStack[n] + min(get_memo(n + 2, memo), get_memo(n + 3, memo), get_memo(n + 4, memo))
			y = bStack[n] + bStack[n + 1] + min(get_memo(n + 3, memo), get_memo(n + 4, memo), get_memo(n + 5, memo))
			z = bStack[n] + bStack[n + 1] + bStack[n + 2] + min(get_memo(n + 4, memo), get_memo(n + 5, memo), get_memo(n + 6, memo))
			memo[n] = max(x, y, z)
	return memo[0]
T = int(input())
for t in range(T):
	N = int(input())
	bStack = [int(x) for x in input().split()]
	maxScore = solver(N, bStack)
	print(maxScore)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.reverse()
	summary = [0] * n
	cache = [0] * n
	summary[0] = arr[0]
	for i in range(1, n):
		summary[i] = summary[i - 1] + arr[i]
	for i in range(3):
		cache[i] = summary[i]
	for i in range(3, n):
		cache[i] = max(summary[i] - cache[i - 1], summary[i] - cache[i - 2], summary[i] - cache[i - 3])
	print(cache[-1])


def sol(bricks):
	if len(bricks) <= 3:
		return sum(bricks)
	solutions = [[0] * len(bricks), [0] * len(bricks)]
	solutions[1][-1] = solutions[0][-1] = sum(bricks[-1:])
	solutions[1][-2] = solutions[0][-2] = sum(bricks[-2:])
	solutions[1][-3] = solutions[0][-3] = sum(bricks[-3:])
	index = len(bricks) - 4
	while index >= 0:
		solutions[0][index] = max(sum(bricks[index:index + 3]) - solutions[1][index + 3], sum(bricks[index:index + 2]) - solutions[1][index + 2], sum(bricks[index:index + 1]) - solutions[1][index + 1])
		solutions[1][index] = max(sum(bricks[index:index + 3]) - solutions[0][index + 3], sum(bricks[index:index + 2]) - solutions[0][index + 2], sum(bricks[index:index + 1]) - solutions[0][index + 1])
		index -= 1
	return solutions[0][0]
t = int(input())
for test in range(t):
	n = int(input())
	bricks = list(map(int, input().split()))
	table = {}
	print((sum(bricks) + sol(bricks)) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	ar = input().split()
	ar = [int(e) for e in ar]
	for l in range(n // 2):
		temp = ar[n - 1 - l]
		ar[n - 1 - l] = ar[l]
		ar[l] = temp
	b = []
	m = []
	b.append(ar[0])
	m.append(0)
	for j in range(1, n):
		b.append(ar[j] + b[j - 1])
		m.append(0)
	m[0] = ar[0]
	m[1] = ar[0] + ar[1]
	m[2] = ar[0] + ar[1] + ar[2]
	m[3] = ar[1] + ar[2] + ar[3]
	for j in range(4, n):
		a = ar[j] + (b[j - 1] - m[j - 1])
		c = ar[j] + ar[j - 1] + (b[j - 2] - m[j - 2])
		d = ar[j] + ar[j - 1] + ar[j - 2] + b[j - 3] - m[j - 3]
		m[j] = max(a, c, d)
	print(m[n - 1])


t = int(input())
for i in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	num = num[::-1]
	me = [0 for i in range(n)]
	opp = [0 for i in range(n)]
	me[0] = num[0]
	me[1] = num[1] + num[0]
	me[2] = num[2] + num[1] + num[0]
	me[3] = num[3] + num[2] + num[1]
	opp[3] = num[0]
	if num[0] > num[2] + num[3]:
		me[4] = num[0] + num[4]
		opp[4] = num[1] + num[2] + num[3]
	else:
		me[4] = num[4] + num[2] + num[3]
		opp[4] = num[0] + num[1]
	for j in range(5, n):
		if num[j] + opp[j - 1] >= num[j] + num[j - 1] + opp[j - 2] and num[j] + opp[j - 1] >= num[j] + num[j - 1] + num[j - 2] + opp[j - 3]:
			me[j] = num[j] + opp[j - 1]
			opp[j] = me[j - 1]
		elif num[j] + opp[j - 1] <= num[j] + num[j - 1] + opp[j - 2] and num[j] + num[j - 1] + opp[j - 2] >= num[j] + num[j - 1] + num[j - 2] + opp[j - 3]:
			me[j] = num[j] + num[j - 1] + opp[j - 2]
			opp[j] = me[j - 2]
		else:
			me[j] = num[j] + num[j - 1] + num[j - 2] + opp[j - 3]
			opp[j] = me[j - 3]
	print(me[n - 1])


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = arr[::-1]
	p1 = [0 for x in range(n)]
	p2 = [0 for x in range(n)]
	(p1[0], p1[1], p1[2], p1[3], p1[4]) = (arr[0], arr[1] + arr[0], arr[0] + arr[1] + arr[2], arr[3] + arr[1] + arr[2], arr[4] + arr[3] + arr[2] if arr[0] < arr[2] + arr[3] else arr[0] + arr[4])
	(p2[0], p2[1], p2[2], p2[3], p2[4]) = (0, 0, 0, arr[0], arr[1] + arr[3] + arr[2] if arr[0] >= arr[2] + arr[3] else arr[0] + arr[1])
	for i in range(5, n):
		a = arr[i] + p2[i - 1]
		b = arr[i] + arr[i - 1] + p2[i - 2]
		c = arr[i] + arr[i - 1] + arr[i - 2] + p2[i - 3]
		if a >= b and a >= c:
			(p1[i], p2[i]) = (a, p1[i - 1])
		elif a >= b and a < c:
			(p1[i], p2[i]) = (c, p1[i - 3])
		elif a <= b and b >= c:
			(p1[i], p2[i]) = (b, p1[i - 2])
		elif a <= b and b <= c:
			(p1[i], p2[i]) = (c, p1[i - 3])
		else:
			print('No match')
	print(p1[n - 1])


def cumsum(it):
	total = 0
	for x in it:
		total += x
		yield total
t = int(input())
for i in range(0, t):
	n = int(input())
	bricks = list(reversed(list(map(int, input().split(' ')))))
	if n < 4:
		print(sum(bricks))
	total = list(cumsum(bricks))
	p = total[0:3]
	for i in range(3, n):
		p.append(total[i] - min(p[-3:]))
	print(p[-1])


def bricks(a):
	length = len(a)
	bsum = [0] * length
	dp = [0] * length
	bsum[length - 1] = a[length - 1]
	bsum[length - 2] = a[length - 2] + bsum[length - 1]
	bsum[length - 3] = a[length - 3] + bsum[length - 2]
	dp[length - 1] = bsum[length - 1]
	dp[length - 2] = bsum[length - 2]
	dp[length - 3] = bsum[length - 3]
	for i in range(length - 4, -1, -1):
		bsum[i] = a[i] + bsum[i + 1]
		one = a[i] + bsum[i + 1] - dp[i + 1]
		two = a[i] + a[i + 1] + bsum[i + 2] - dp[i + 2]
		three = a[i] + a[i + 1] + a[i + 2] + bsum[i + 3] - dp[i + 3]
		dp[i] = max(one, two, three)
	return dp[0]
for i in range(int(input())):
	input()
	print(bricks([int(x) for x in input().split()]))


__author__ = 'deepak Singh Mehta(approach_by agutowski :))'
tests = int(input())
for _ in range(tests):
	n = int(input())
	suff = best = [0] * (n + 3)
	arr = list(map(int, input().split()))
	for i in range(n - 1, -1, -1):
		suff[i] = suff[i + 1] + arr[i]
	for i in range(n - 1, -1, -1):
		best[i] = suff[i] - min(best[i + 1:i + 4])
	print(best[0])


def solve(n, scores):
	total = [0] * n
	dp = [0] * n
	total[-1] = scores[-1]
	for i in range(n - 2, -1, -1):
		total[i] = total[i + 1] + scores[i]
	dp[-3:] = total[-3:]
	for i in range(n - 4, -1, -1):
		for j in range(1, 4):
			dp[i] = max(dp[i], total[i] - dp[i + j])
	return dp[0]

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		scores = list(map(int, input().split()))
		print(solve(n, scores))
main()


T = int(input())
for t in range(T):
	N = int(input())
	bricks = list(map(int, input().split(' ')))
	dp = [(0, 0) for i in range(N + 1)]
	for n in range(N - 1, -1, -1):
		for b in (1, 2, 3):
			if n + b <= N:
				val = (sum(bricks[n:n + b]) + dp[n + b][1], dp[n + b][0])
				dp[n] = max(dp[n], val)
	print(dp[0][0])


def bestScore(A, N):
	B = [0] * (N + 1)
	M = [0] * (N + 1)
	for i in range(N - 1, -1, -1):
		cand = []
		for j in range(i, min(N, i + 3)):
			e = j + 1
			cand.append((sum(A[i:e]) + M[e], e))
		(value, r) = max(cand)
		B[i] = value
		M[i] = B[r]
	return B[0]
T = int(input())
for _ in range(T):
	N = int(input())
	A = tuple(map(int, input().split()))
	print(bestScore(A, N))


from collections import defaultdict

def game(bricks):
	table = defaultdict(int)
	n = len(bricks)
	bricks.extend([0, 0])
	for i in range(n - 1, -1, -1):
		table[i] = max(bricks[i] + min(table[i + 2], table[i + 3], table[i + 4]), bricks[i] + bricks[i + 1] + min(table[i + 3], table[i + 4], table[i + 5]), bricks[i] + bricks[i + 1] + bricks[i + 2] + min(table[i + 4], table[i + 5], table[i + 6]))
	return table[0]
num_tests = int(input().strip())
for i in range(num_tests):
	num_bricks = int(input().strip())
	scores = [int(i) for i in input().strip().split(' ')]
	print(game(scores))


import sys
sys.setrecursionlimit(1000000)
T = int(input())

def max_score1(stack, acc, ptr, dp):
	if dp[ptr] == -1:
		if ptr < 3:
			dp[ptr] = acc[ptr]
		else:
			opt1 = max_score(stack, acc, ptr - 1, dp)
			opt2 = max_score(stack, acc, ptr - 2, dp)
			opt3 = max_score(stack, acc, ptr - 3, dp)
			dp[ptr] = max(acc[ptr - 1] - opt1 + stack[ptr], acc[ptr - 2] - opt2 + stack[ptr] + stack[ptr - 1], acc[ptr - 3] - opt3 + stack[ptr] + stack[ptr - 1] + stack[ptr - 2])
	return dp[ptr]

def max_score(stack):
	if len(stack) <= 3:
		return sum(stack)
	n = len(stack)
	dp = [0 for i in range(n)]
	acc = stack[:]
	for i in range(n - 2, -1, -1):
		acc[i] = acc[i] + acc[i + 1]
	(dp[n - 1], dp[n - 2], dp[n - 3]) = (acc[n - 1], acc[n - 2], acc[n - 3])
	for i in range(4, n + 1):
		dp[n - i] = max(acc[n - i + 1] - dp[n - i + 1] + stack[n - i], acc[n - i + 2] - dp[n - i + 2] + stack[n - i] + stack[n - i + 1], acc[n - i + 3] - dp[n - i + 3] + stack[n - i] + stack[n - i + 1] + stack[n - i + 2])
	return dp[0]
for i in range(T):
	N = int(input())
	stack = [int(n) for n in input().split()]
	print(max_score(stack))


def game_bricks(bricks, n):
	states = [[0] * n, [0] * n]
	for i in range(n - 1, -1, -1):
		states[0][i] = max(bricks[i] + (states[1][i + 1] if i < n - 1 else 0), bricks[i] + (bricks[i + 1] if i < n - 1 else 0) + (states[1][i + 2] if i < n - 2 else 0), bricks[i] + (bricks[i + 1] if i < n - 1 else 0) + (bricks[i + 2] if i < n - 2 else 0) + (states[1][i + 3] if i < n - 3 else 0))
		states[1][i] = min(states[0][i + 1] if i < n - 1 else 0, states[0][i + 2] if i < n - 2 else 0, states[0][i + 3] if i < n - 3 else 0)
	return states[0][0]
for i in range(int(input())):
	n = int(input())
	bricks = [int(i) for i in input().split()]
	print(game_bricks(bricks, n))


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	b.reverse()
	sum = [0] * (n + 1)
	for i in range(1, n + 1):
		sum[i] = sum[i - 1] + b[i - 1]
	dp = [0] * (n + 1)
	dp[1] = b[0]
	dp[2] = b[1] + dp[1]
	dp[3] = b[2] + dp[2]
	dp[4] = b[3] + b[2] + b[1]
	for i in range(5, n + 1):
		dp[i] = max(b[i - 1] + sum[i - 1] - dp[i - 1], b[i - 1] + b[i - 2] + sum[i - 2] - dp[i - 2], b[i - 1] + b[i - 2] + b[i - 3] + sum[i - 3] - dp[i - 3])
	print(dp[n])


for _ in range(int(input())):
	input()
	arr = list(reversed([int(x) for x in input().split()]))
	opt = [0, arr[0]]
	running_total = arr[0]
	if len(arr) > 1:
		opt.append(arr[1] + arr[0])
		running_total += arr[1]
	if len(arr) > 2:
		opt.append(arr[2] + arr[1] + arr[0])
		running_total += arr[2]
	for i in range(3, len(arr)):
		running_total += arr[i]
		take_one = running_total - opt[-1]
		take_two = running_total - opt[-2]
		take_three = running_total - opt[-3]
		opt.append(max([take_one, take_two, take_three]))
	print(opt[-1])