You are given N integers A_{1}, A_{2}, \ldots, A_{N}.

You can perform the following operation any number of times:

Select any index i such that 1 ≤ i ≤ (N-1);
Subtract 1 from A_{i} and 2 from A_{i+1}.

Find the smallest possible value of |A_{1}| + |A_{2}| + \ldots + |A_{N}| you can achieve after performing any number of given operations.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N — the number of integers.
- The second line of each test case contains N integers A_{1}, A_{2}, \ldots, A_{N}.

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

For each test case, output a single integer — the smallest possible value of |A_{1}| + |A_{2}| + \ldots + |A_{N}| you can achieve after performing any number of given operations.

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

$1 ≤ T ≤ 100000$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$-10^{9} ≤A_{i} ≤10^{9}$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
2
2 4
3
1 1 1
6
-4 2 -4 2 -4 2
1
-100000000

----- Sample Output 1 ------ 
0
2
15
100000000

----- explanation 1 ------ 
Test case $1$: We can apply the operation for $i = 1$. Thus, the array becomes $A = [1, 2]$. On applying the operation again for $i=1$, the array becomes $A = [0, 0]$. Thus, the value of $|A_{1}| + |A_{2}| = 0$. It can be shown that this is the smallest possible value of $|A_{1}| + |A_{2}|$. 

Test case $2$: Apply the operation for $i = 1$. The array becomes $A = [0, -1, 1]$. Thus, the value $|A_{1}+|A_{2}|+|A_{3}| = 0+1+1 = 2$.

Test case $3$: We apply three operations on indices $1, 3,$ and $5$ respectively. Thus, the final array becomes $A = [-5, 0, -5, 0, -5, 0]$. The value $|A_{1}| + |A_{2}| + \ldots + |A_{6}| = 15$.

Test case $4$: We cannot apply any operation on the array as we cannot choose any valid index.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in reversed(range(1, n)):
		if a[i] > 0:
			moves = a[i] // 2
			a[i] -= 2 * moves
			a[i - 1] -= moves
	for i in reversed(range(1, n)):
		if a[i] > 0 and a[i - 1] > 0:
			a[i] -= 2
			a[i - 1] -= 1
	print(sum((abs(x) for x in a)))


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	for i in reversed(range(1, n)):
		if arr[i] > 0:
			x = arr[i] // 2
			arr[i] -= 2 * x
			arr[i - 1] -= x
	for i in reversed(range(1, n)):
		if arr[i] > 0 and arr[i - 1] > 0:
			arr[i] -= 2
			arr[i - 1] -= 1
	print(sum((abs(i) for i in arr)))


def f(n, arr):
	k = 0
	for j in range(n - 2, -1, -1):
		if arr[j + 1] <= 0:
			k = 0
			continue
		if arr[j + 1] % 2 == 0 or k == 1:
			arr[j] -= arr[j + 1] // 2
			arr[j + 1] = 0
			k = 0
		elif j == 0:
			if arr[j] - arr[j + 1] // 2 > 0:
				arr[j] -= arr[j + 1] // 2 + 1
				arr[j + 1] = -1
			else:
				arr[j] -= arr[j + 1] // 2
				arr[j + 1] = 1
		else:
			arr[j] -= arr[j + 1] // 2
			arr[j + 1] = 1
			k = 1
	return sum([abs(el) for el in arr])
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(el) for el in input().split(' ')]
	print(f(n, arr))


def find_best_sub(arr, i, negative=False):
	(a, b) = (arr[i - 1], arr[i])
	if b <= 0:
		return 0
	cand = b // 2
	if a > cand and b % 2 == 1 and negative:
		cand += 1
	return cand

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		for i in range(n - 1, 0, -1):
			x = find_best_sub(a, i)
			a[i - 1] -= x
			a[i] -= 2 * x
		for i in range(n - 1, 0, -1):
			x = find_best_sub(a, i, negative=True)
			a[i - 1] -= x
			a[i] -= 2 * x
		print(sum(map(abs, a)))
main()


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


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	S = 0
	for i in range(N - 1, 0, -1):
		if A[i] > 0:
			q = int(A[i] / 2)
			A[i] = A[i] % 2
			A[i - 1] -= q
	for i in range(N - 1, 0, -1):
		if A[i] == 1 and A[i - 1] > 0:
			A[i] -= 2
			A[i - 1] -= 1
	for i in A:
		S += abs(i)
	print(S)


import time
import sys
import math
mod = 1000000007
from collections import defaultdict as dd
from collections import Counter
from itertools import accumulate
from functools import lru_cache
inty = lambda : int(input())
stringy = lambda : input().strip()
mappy = lambda : map(int, input().strip().split())
fmappy = lambda : map(float, input().strip().split())
listy = lambda : list(map(int, input().strip().split()))
sys.setrecursionlimit(10 ** 6)
tick = lambda : time.perf_counter()
logg = lambda a, b: math.log(a) / math.log(b)
prefix = lambda x: list(accumulate(x))
sign = lambda x, y: x >= 0 and y >= 0 or (x < 0 and y < 0)
T = inty()
for _ in range(T):
	n = inty()
	nums = listy()
	for i in range(n - 1, 0, -1):
		if nums[i] > 0:
			till = nums[i] // 2
			nums[i] -= 2 * till
			nums[i - 1] -= till
	for i in range(n - 1, 0, -1):
		if nums[i] == 1 and nums[i - 1] > 0:
			nums[i - 1] -= 1
	res = 0
	for i in range(n):
		res += abs(nums[i])
	print(res)


test = int(input())
while test:
	test -= 1
	N = int(input())
	A = list(map(int, input().split()))
	for i in range(N - 1, 0, -1):
		if A[i] > 0:
			k = A[i] // 2
			A[i] -= 2 * k
			A[i - 1] -= k
	for i in range(N - 1):
		if A[i] > 0 and A[i + 1] > 0:
			A[i] -= 1
			A[i + 1] -= 2
	ans = 0
	for i in A:
		ans += abs(i)
	print(ans)


N = int(input())
while N > 0:
	n = int(input())
	a = input()
	b = 0
	a = a.split()
	a = list(map(lambda x: int(x), a))
	m = n
	if n == 1:
		if a[0] < 0:
			a[0] = a[0] * -1
		print(a[0])
	else:
		while n > 1:
			if a[n - 1] >= 2:
				div = a[n - 1] // 2
				a[n - 2] = a[n - 2] - div
				a[n - 1] = a[n - 1] % 2
			n = n - 1
		n = m
		while n > 1:
			if a[n - 1] == 1 and a[n - 2] > 0:
				a[n - 2] = a[n - 2] - 1
				a[n - 1] = a[n - 1] - 2
			n = n - 1
		for i in range(0, m):
			if a[i] < 0:
				a[i] = a[i] * -1
			b = b + a[i]
		print(b)
	N = N - 1


n = int(input())
for z in range(n):
	size = int(input())
	arr = [int(i) for i in input().split()]
	for i in range(size - 1, 0, -1):
		if arr[i] > 0:
			k = arr[i] // 2
			arr[i] = arr[i] - 2 * k
			arr[i - 1] = arr[i - 1] - k
	for i in range(size - 1, 0, -1):
		if arr[i] > 0 and arr[i - 1] > 0:
			arr[i] -= 2
			arr[i - 1] -= 1
	sum = 0
	for i in arr:
		sum += abs(i)
	print(sum)


from sys import stdin

def sp(n, a):
	if n == 1:
		return abs(a[0])
	ans = 0
	for i in range(n - 1, 0, -1):
		a1 = a[i - 1]
		a2 = a[i]
		if a2 <= 0:
			continue
		z = a2 // 2
		a[i] -= z * 2
		a[i - 1] -= z
	for i in range(n - 1, 0, -1):
		if a[i] > 0 and a[i - 1] > 0:
			a[i] -= 2
			a[i - 1] -= 1
	return sum([abs(x) for x in a])
t = int(stdin.readline().strip())
for i in range(t):
	n = int(stdin.readline().strip())
	a = [int(x) for x in stdin.readline().split()]
	print(sp(n, a))


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(n - 1):
		if arr[n - i - 1] > 1 and arr[n - i - 1] % 2 == 0:
			div = math.floor(arr[n - i - 1] / 2)
			arr[n - i - 1] = 0
			arr[n - i - 2] -= div
		elif arr[n - i - 1] > 1 and arr[n - i - 1] % 2 != 0:
			div = math.floor(arr[n - i - 1] / 2)
			arr[n - i - 1] = 1
			arr[n - i - 2] -= div
	for i in range(n - 1):
		if arr[n - i - 2] > 0 and arr[n - i - 1] > 0:
			arr[n - i - 2] -= 1
			arr[n - i - 1] -= 2
		arr[n - i - 1] = abs(arr[n - i - 1])
	arr[0] = abs(arr[0])
	print(sum(arr))


for i in range(int(input())):
	N = int(input())
	arr = [int(x) for x in input().split()]
	for i in range(len(arr) - 1, 0, -1):
		if arr[i] < 0:
			continue
		x = arr[i] // 2
		arr[i] = arr[i] - x * 2
		arr[i - 1] = arr[i - 1] - x
	for i in range(len(arr) - 1, 0, -1):
		if arr[i] > 0 and arr[i - 1] > 0:
			arr[i] -= 2
			arr[i - 1] -= 1
	sum = 0
	for i in arr:
		sum += abs(i)
	print(sum)


for test in range(int(input())):
	n = int(input())
	a = [int(ai) for ai in input().split()]
	for i in range(n - 1, 0, -1):
		if a[i] >= 2 and a[i - 1] >= 1:
			substract = min(a[i] // 2, a[i - 1])
			a[i] -= 2 * substract
			a[i - 1] -= 1 * substract
	for i in range(n - 1, 0, -1):
		if a[i] >= 2:
			substract = a[i] // 2
			a[i] -= 2 * substract
			a[i - 1] -= 1 * substract
	for i in range(n - 1, 0, -1):
		if a[i] == 1 and a[i - 1] >= 1:
			a[i] -= 2
			a[i - 1] -= 1
	print(sum((abs(ai) for ai in a)))


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


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


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(abs(a[0]))
	else:
		for i in range(n - 1, 0, -1):
			if a[i] > 0:
				moves = a[i] // 2
				a[i] -= 2 * moves
				a[i - 1] -= moves
		for i in range(n - 1, 0, -1):
			if a[i] > 0 and a[i - 1] > 0:
				a[i] -= 2
				a[i - 1] -= 1
		print(sum((abs(x) for x in a)))
	t -= 1


import sys
import math
from collections import Counter
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = [int(i) for i in sys.stdin.readline().split()]
	if n == 1:
		print(abs(a[0]))
	else:
		ans = 0
		for i in reversed(range(1, n)):
			if a[i] > 0:
				moves = a[i] // 2
				a[i] -= 2 * moves
				a[i - 1] -= moves
		for i in reversed(range(1, n)):
			if a[i] > 0 and a[i - 1] > 0:
				a[i] -= 2
				a[i - 1] -= 1
		print(sum((abs(x) for x in a)))


import sys
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 v(k, val1, val2):
	val1 -= k
	val2 -= 2 * k
	return abs(val1) + abs(val2)

def fun(val1, val2):
	if val2 <= 0:
		return (val1, val2)
	x = val2 // 2
	m1 = v(x, val1, val2)
	return (val1 - x, val2 - 2 * x)
for _ in range(inp()):
	n = inp()
	arr = inlt()
	if n == 1:
		print(abs(arr[0]))
	else:
		for i in range(n - 2, -1, -1):
			(arr[i], arr[i + 1]) = fun(arr[i], arr[i + 1])
		sm = 0
		for i in range(n - 1, 0, -1):
			if arr[i] == 1 and arr[i - 1] > 0:
				arr[i] = -1
				arr[i - 1] -= 1
		for i in range(n):
			sm += abs(arr[i])
		print(sm)


from math import *
from bisect import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 1, 0, -1):
		if a[i] > 0:
			t = a[i] // 2
			a[i - 1] -= t
			a[i] -= 2 * t
	for i in range(n - 1, 0, -1):
		if a[i] > 0 and a[i - 1] > 0:
			a[i - 1] -= 1
			a[i] -= 2
	sum_ = 0
	for i in a:
		sum_ += abs(i)
	print(sum_)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	for i in range(N - 1, 0, -1):
		if A[i] > 0:
			val = A[i]
			A[i - 1] -= val // 2
			A[i] = val % 2
	for i in range(N - 2, -1, -1):
		if A[i] > 0 and A[i + 1] == 1:
			A[i] -= 1
			A[i + 1] -= 2
	ans = 0
	for i in A:
		ans += abs(i)
	print(ans)


def op(a, b):
	if abs(a - 2) + abs(b - 1) < abs(a) + abs(b):
		return True
	return False
import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().split()))
	ans = 0
	if n == 1:
		print(abs(arr[0]))
	else:
		i = n - 1
		while i > 0:
			if arr[i] > 0 and op(arr[i], arr[i - 1]):
				if arr[i] % 2 == 0:
					arr[i - 1] -= arr[i] // 2
					arr[i] = 0
				else:
					arr[i - 1] -= arr[i] // 2
					arr[i] = 1
			i -= 1
		i = n - 1
		while i > 0:
			if arr[i] > 0 and op(arr[i], arr[i - 1]):
				arr[i] = -1
				arr[i - 1] -= 1
			i -= 1
		for i in arr:
			ans += abs(i)
		sys.stdout.write(str(ans) + '\n')


from sys import stdin
input = stdin.readline

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

def li():
	return list(map(int, input().split()))
from math import sqrt

def perfect_sq(n):
	x = int(sqrt(n))
	while x * x < n:
		x += 1
	while x * x > n:
		x -= 1
	return x * x == n
for _ in range(ii()):
	n = ii()
	a = li()
	for i in range(n - 2, -1, -1):
		if a[i + 1] > 0:
			moves = a[i + 1] // 2
			a[i + 1] -= 2 * moves
			a[i] -= moves
	for i in range(n - 2, -1, -1):
		if a[i] > 0 and a[i + 1] > 0:
			a[i + 1] -= 2
			a[i] -= 1
	ans = 0
	for i in a:
		ans += abs(i)
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 1, 0, -1):
		if a[i] > 0:
			a[i - 1] -= a[i] // 2
			a[i] %= 2
	for i in range(n - 1, 0, -1):
		if a[i] > 0 and a[i - 1] > 0:
			a[i] -= 2
			a[i - 1] -= 1
	res = 0
	for i in a:
		res += abs(i)
	print(res)


import numpy as np
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in reversed(range(1, n)):
		if a[i] > 0:
			moves = a[i] // 2
			a[i] -= 2 * moves
			a[i - 1] -= moves
	for i in reversed(range(1, n)):
		if a[i] > 0 and a[i - 1] > 0:
			a[i] -= 2
			a[i - 1] -= 1
	print(np.sum(np.abs(a)))


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)
t = ri()
for test in range(t):
	n = ri()
	arr = rl()
	i = n - 1
	while i >= 1:
		if arr[i] > 0:
			x = arr[i] // 2
			arr[i - 1] -= x
			arr[i] -= 2 * x
		i -= 1
	ans = 0
	i = n - 1
	while i >= 1:
		if arr[i] == 1 and arr[i - 1] > 0:
			arr[i - 1] -= 1
			arr[i] -= 2
		i -= 1
	for i in arr:
		ans += abs(i)
	print(ans)


T = int(input())
for _ in range(T):
	n = int(input())
	nums = list(map(int, input().split()))
	for i in range(n - 1, 0, -1):
		if nums[i] > 0:
			hf = nums[i] // 2
			nums[i] -= 2 * hf
			nums[i - 1] -= hf
	for i in range(n - 1, 0, -1):
		if nums[i] == 1 and nums[i - 1] > 0:
			nums[i] -= 2
			nums[i - 1] -= 1
	res = 0
	for num in nums:
		res += abs(num)
	print(res)


t = int(input())
res = []
for _ in range(t):
	n = int(input())
	nums = [int(x) for x in input().split()]
	for i in range(n - 1, 0, -1):
		if nums[i] > 0:
			times = nums[i] // 2
			nums[i] -= 2 * times
			nums[i - 1] -= times
	for i in range(n - 1, 0, -1):
		if nums[i] > 0 and nums[i - 1] > 0:
			nums[i] -= 2
			nums[i - 1] -= 1
	res.append(sum((abs(x) for x in nums)))
for val in res:
	print(val)


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


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


for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	min_su = 0
	for k in range(n - 2, -1, -1):
		if li[k + 1] > 0:
			va = li[k + 1] // 2
			li[k] -= va
			li[k + 1] -= 2 * va
	for k in range(n - 2, -1, -1):
		if li[k] > 0 and li[k + 1] == 1:
			li[k] -= 1
			li[k + 1] -= 2
	for i in li:
		min_su += abs(i)
	print(min_su)


for _ in range(int(input())):
	N = int(input())
	nums = list(map(int, input().split()))
	for i in range(N - 1, 0, -1):
		if nums[i] >= 2:
			nums[i - 1] = nums[i - 1] - nums[i] // 2
			nums[i] = nums[i] % 2
	for i in range(len(nums) - 1, 0, -1):
		if nums[i] >= 1 and nums[i - 1] >= 1:
			nums[i - 1] = nums[i - 1] - 1
			nums[i] = nums[i] - 2
	print(sum([abs(x) for x in nums]))


for _ in range(int(input())):
	N = int(input())
	nums = list(map(int, input().split()))
	s = abs(nums[0]) if N == 1 else (2 * 10) ** 5
	for i in range(len(nums) - 1, 0, -1):
		if nums[i] >= 2:
			nums[i - 1] = nums[i - 1] - nums[i] // 2
			nums[i] = nums[i] % 2
	for i in range(len(nums) - 1, 0, -1):
		if nums[i] >= 1 and nums[i - 1] >= 1:
			nums[i - 1] = nums[i - 1] - 1
			nums[i] = nums[i] - 2
	print(sum([abs(x) for x in nums]))


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(abs(l[0]))
	else:
		for i in range(n - 1, 0, -1):
			if l[i] <= 0:
				continue
			else:
				m = l[i] // 2
				l[i] %= 2
				l[i - 1] -= m
		for i in range(n - 1, 0, -1):
			if l[i] == 1 and l[i - 1] > 0:
				l[i - 1] -= 1
				l[i] -= 2
		s = 0
		for i in range(n):
			s += abs(l[i])
		print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	for i in range(n - 1, 0, -1):
		if a[i] > 0:
			count = a[i] // 2
			a[i] = a[i] - 2 * count
			a[i - 1] = a[i - 1] - 1 * count
	for i in range(n - 1):
		if a[i] > 0 and a[i + 1] > 0:
			a[i] = a[i] - 1
			a[i + 1] = a[i + 1] - 2
	sum1 = 0
	for i in range(n):
		sum1 += abs(a[i])
	print(sum1)


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


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(n - 1, 0, -1):
		if l[i] <= 0:
			ans += abs(l[i])
		else:
			ans += l[i] % 2
			l[i - 1] -= l[i] // 2
			if l[i - 1] > 0 and l[i] % 2 == 1:
				if i > 1:
					l[i - 1] -= l[i - 1] % 2
				else:
					l[i - 1] -= 1
	ans += abs(l[0])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(abs(a[0]))
		continue
	else:
		for i in range(n - 1, 0, -1):
			if a[i] < 1:
				continue
			elif a[i] % 2 == 0 and a[i] >= 2:
				diff = a[i] // 2
				a[i] = 0
				a[i - 1] -= diff
			elif a[i] % 2 != 0 and a[i] > 1:
				diff = (a[i] - 1) // 2
				a[i] = 1
				a[i - 1] -= diff
		for i in range(n - 1, 0, -1):
			if a[i] == 1:
				if a[i - 1] > 0:
					a[i] = -1
					a[i - 1] -= 1
		ans = 0
		for i in range(n):
			ans += abs(a[i])
		print(ans)


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


import sys
from math import sqrt, gcd, factorial, ceil, floor, pi
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 10 ** 9 + 7
for _ in range(I()):
	n = I()
	a = L()
	ans = 0
	for i in range(n - 1)[::-1]:
		if a[i + 1] <= 0:
			continue
		x = a[i + 1] // 2
		a[i] -= x
		a[i + 1] -= 2 * x
	for i in range(n - 1)[::-1]:
		if a[i] > 0 and a[i + 1] == 1:
			a[i] -= 1
			a[i + 1] -= 2
	for i in a:
		ans += abs(i)
	print(ans)


def main():
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		for i in reversed(range(1, n)):
			if l[i] > 0:
				m = l[i] // 2
				l[i - 1] -= m
				l[i] -= 2 * m
		for i in reversed(range(1, n)):
			if l[i] == 1 and l[i - 1] > 0:
				l[i - 1] -= 1
				l[i] -= 2
		print(sum((abs(j) for j in l)))
main()


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	s = 0
	for i in range(n - 1, 0, -1):
		if arr[i] > 0:
			temp = arr[i] // 2
			arr[i - 1] -= temp
			arr[i] -= temp * 2
	for i in range(n - 1, 0, -1):
		if arr[i] > 0 and arr[i - 1] > 0:
			arr[i - 1] -= 1
			arr[i] -= 2
	for i in range(0, n):
		s += abs(arr[i])
	print(s)
	t -= 1


import math
from bisect import bisect, bisect_left, bisect_right
import heapq
from math import gcd, floor, sqrt, log
from collections import defaultdict as ddc
from collections import Counter

def intin():
	return int(input())

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

def strin():
	return input().split()
INF = 10 ** 20
mod = 1000000007

def LIS(arr, n):
	dp = [10 ** 9] * (n + 1)
	for ele in arr:
		dp[bisect_left(dp, ele)] = ele
	return bisect_left(dp, 10 ** 9)

def exponentiation(bas, exp, mod=1000000007):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def process(arr, n):
	if n == 1:
		return abs(arr[0])
	ans = 0
	for i in range(n - 1, 0, -1):
		if arr[i] > 0:
			arr[i - 1] -= arr[i] // 2
			arr[i] %= 2
	for i in range(n - 1):
		if arr[i] > 0 and arr[i + 1] > 0:
			while arr[i + 1] > 0:
				arr[i] -= 1
				arr[i + 1] -= 2
		ans += abs(arr[i])
	ans += abs(arr[n - 1])
	return ans

def main():
	for _ in range(int(input())):
		n = intin()
		arr = list(mapin())
		print(process(arr, n))
main()


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


import math

def new_sum(lst):
	Sum = 0
	for num in lst:
		if num < 0:
			Sum += -num
		else:
			Sum += num
	return Sum

def test():
	N = int(input())
	nums = list(map(int, input().split()))
	last_sum = new_sum(nums)
	for i in range(len(nums) - 1, 0, -1):
		if nums[i] >= 2:
			nums[i - 1] = nums[i - 1] - nums[i] // 2
			nums[i] = nums[i] % 2
	for i in range(len(nums) - 1, 0, -1):
		if nums[i] >= 1 and nums[i - 1] >= 1:
			nums[i - 1] = nums[i - 1] - 1
			nums[i] = nums[i] - 2
	print(new_sum(nums))
tests = int(input())
for i in range(tests):
	test()


def codeforces(arr, n):
	for i in range(n - 1, 0, -1):
		if arr[i] >= 2 and arr[i - 1] >= 1:
			x = min(arr[i] // 2, arr[i - 1])
			arr[i - 1] -= x
			arr[i] -= 2 * x
	for i in range(n - 1, 0, -1):
		if arr[i] >= 2:
			x = arr[i] // 2
			arr[i - 1] -= x
			arr[i] = arr[i] % 2
		if arr[i] == 1 and arr[i - 1] > 0:
			arr[i] = -1
			arr[i - 1] -= 1
	ans = 0
	for i in arr:
		ans += abs(i)
	return ans
t = int(input())
for test in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	print(codeforces(arr, n))


import math
t = int(input())
for _ in range(t):
	N = int(input())
	arr = list(map(int, input().split()))
	for i in range(N - 1, 0, -1):
		second = arr[i]
		if second >= 1:
			if second >= 2:
				mult = math.floor(second / 2)
				arr[i] = second - 2 * mult
				arr[i - 1] = arr[i - 1] - mult
			if arr[i] == 1 and arr[i - 1] >= 1 and (arr[i - 1] % 2 == 1):
				arr[i] = -1
				arr[i - 1] -= 1
			elif arr[i] == 1 and arr[i - 1] >= 1 and (i == 1):
				arr[0] -= 1
				arr[i] = -1
	sum = 0
	for i in range(N):
		sum += abs(arr[i])
	print(sum)


iter = int(input())
for z in range(iter):
	n = int(input())
	a = list(map(int, input().split(' ')))
	ans = 0
	for i in range(n - 1, 0, -1):
		mult = 0
		if a[i] > 0:
			if a[i] & 1:
				mult = a[i] // 2
				a[i] = 1
			else:
				mult = a[i] // 2
				a[i] = 0
		a[i - 1] -= mult
	for i in range(n - 1, 0, -1):
		if a[i] == 1 and a[i - 1] > 0:
			a[i - 1] -= 1
	for i in range(n):
		ans += abs(a[i])
	print(ans)


t = int(input())
for e in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	i = len(l) - 2
	while i >= 0:
		if l[i + 1] >= 0:
			q1 = int(l[i + 1] / 2)
			q2 = l[i + 1] % 2
			l[i] -= q1 * 1
			l[i + 1] -= 2 * q1
		i -= 1
	s = 0
	for i in range(n - 2, -1, -1):
		if l[i + 1] == 1 and l[i] > 0:
			l[i + 1] = -1
			l[i] -= 1
	for i in l:
		s += abs(i)
	print(s)


for _ in range(int(input())):
	array_len = int(input())
	array = [int(num) for num in input().split()]
	for i in range(array_len - 1, 0, -1):
		if array[i] <= 0:
			continue
		if array[i] >= 2:
			array[i - 1] -= array[i] // 2
			array[i] %= 2
		if array[i] == 1 and array[i - 1] >= 1 and (array[i - 1] % 2 != 0 or i - 1 == 0):
			array[i] -= 2
			array[i - 1] -= 1
	print(sum([abs(num) for num in array]))


import sys, math, heapq, bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
ints = lambda : list(map(int, input().split()))

def gprint(t, ans=''):
	print(f'Case #{t + 1}:', ans)
p = 10 ** 9 + 7
inf = 10 ** 20 + 7
for t in range(int(input())):
	n = int(input())
	a = ints()
	for i in range(n - 1, 0, -1):
		if a[i] > 0:
			x = a[i] // 2
			a[i] = a[i] % 2
			a[i - 1] -= x
	for i in range(n - 1):
		if a[i] > 0 and a[i + 1] > 0:
			a[i] -= 1
			a[i + 1] -= 2
	ans = 0
	for i in a:
		ans += abs(i)
	print(ans)