JJ has an array A initially of length N. He can perform the following operation on A:

1) Pick any index i (1 ≤ i ≤ |A|) such that A_{i} > 1 \\
2) Select any two integers X and Y such that X + Y = A_{i} and X, Y ≥ 1 \\
3) Replace A_{i} with X and Y

Note that the length of the array increases by 1 after each operation.

For example, if A = [4, 6, 7, 2], he can select i = 1 and select X = 1, Y = 3 (since X + Y = A_{1}). After the operation array becomes: [\underline{4}, 6, 7, 2] \rightarrow [\underline{1}, \underline{3}, 6, 7, 2].

JJ wants to make A palindromic. Find the minimum number of operations to do so.

It is guaranteed that A can be converted to a palindromic array by using the above operation.

Note: An array is called a palindrome if it reads the same backwards and forwards, for e.g. [1, 3, 3, 1] and [6, 2, 6] are palindromic.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, output the minimum number of operations to make A palindromic. 

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤A_{i} ≤10^{5}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
4
3 7 6 4
5
1 4 5 4 1
5
1 2 3 4 5

----- Sample Output 1 ------ 
2
0
4

----- explanation 1 ------ 
Test Case 1: We can perform the following operations: 
- $[3, \underline{7}, 6, 4] \xrightarrow{i = 2, X = 1, Y = 6} [3, \underline{1}, \underline{6}, 6, 4]$
- $[3, 1, 6, 6, \underline{4}] \xrightarrow{i = 5, X = 1, Y = 3} [3, 1, 6, 6, \underline{1}, \underline{3}]$

Test Case 2: $A$ is already palindromic.

Difficulty: MEDIUM
Tags: Data structures

Amortized analysis
Skill types: Amortized analysis

Data structures

Starter code:

Solutions:
t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	(i, j, count) = (0, 0, 0)
	h = n // 2
	if n % 2 == 0:
		pass
	else:
		h += 1
	j = n - 1
	while i < j:
		if l[i] == l[j]:
			i += 1
			j -= 1
		elif l[i] > l[j]:
			count += 1
			l[i] = l[i] - l[j]
			j -= 1
		else:
			count += 1
			l[j] = l[j] - l[i]
			i += 1
	print(count)
	t -= 1


t = int(input())
for i in range(t):
	a = int(input())
	arr = list(map(int, input().split()))
	count = 0
	while len(arr) > 1:
		if arr[0] == arr[-1]:
			del arr[0]
			del arr[-1]
		else:
			if arr[0] > arr[-1]:
				arr[0] = arr[0] - arr[-1]
				del arr[-1]
			else:
				arr[-1] = arr[-1] - arr[0]
				del arr[0]
			count = count + 1
	print(count)


from collections import deque
T = int(input())
for t in range(T):
	n = int(input())
	arr = deque(map(int, input().split()))
	ans = 0
	while len(arr) > 1:
		last = len(arr) - 1
		if arr[0] == arr[last]:
			arr.popleft()
			arr.pop()
		elif arr[0] > arr[last]:
			addleft = arr[0] - arr[last]
			arr.popleft()
			arr.pop()
			arr.appendleft(addleft)
			ans += 1
		elif arr[0] < arr[last]:
			addright = arr[last] - arr[0]
			arr.popleft()
			arr.pop()
			arr.append(addright)
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = 0
	y = n - 1
	ans = 0
	while len(a) > 1:
		if a[0] == a[-1]:
			del a[0]
			del a[-1]
		elif a[0] < a[-1]:
			x = a[0]
			y = a[-1]
			del a[0]
			del a[-1]
			a.append(y - x)
			ans += 1
		else:
			a.reverse()
			x = a[0]
			y = a[-1]
			del a[0]
			del a[-1]
			a.append(y - x)
			a.reverse()
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	while len(arr) > 1:
		if arr[0] == arr[-1]:
			del arr[0]
			del arr[-1]
		else:
			if arr[0] > arr[-1]:
				arr[0] = arr[0] - arr[-1]
				del arr[-1]
			else:
				arr[-1] = arr[-1] - arr[0]
				del arr[0]
			count = count + 1
	print(count)


for _ in range(int(input())):
	r = int(input()) - 1
	s = list(map(int, input().split()))
	cout = 0
	l = 0
	while l < r:
		if s[l] != s[r]:
			cout = cout + 1
			if s[l] > s[r]:
				s[l] = s[l] - s[r]
				r = r - 1
			else:
				s[r] = s[r] - s[l]
				l = l + 1
		else:
			r = r - 1
			l = l + 1
	print(cout)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	(s, e, c) = (0, n - 1, 0)
	if n == 1:
		print(c)
	else:
		while s < e:
			if a[s] < a[e]:
				a[e] = a[e] - a[s]
				c += 1
				s += 1
			elif a[s] > a[e]:
				a[s] = a[s] - a[e]
				c += 1
				e -= 1
			else:
				s += 1
				e -= 1
		print(c)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = deque(a)
	count = 0
	while len(a) != 0 and len(a) != 1:
		s1 = a.pop()
		s2 = a.popleft()
		if s2 > s1:
			a.appendleft(s2 - s1)
			count += 1
		elif s1 > s2:
			a.append(s1 - s2)
			count += 1
	print(count)


t = int(input())
for j in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	if n == 1:
		print(0)
	else:
		while len(arr) > 1:
			if arr[0] == arr[-1]:
				arr.pop(-1)
				arr.pop(0)
			else:
				if arr[0] > arr[-1]:
					arr[0] = arr[0] - arr[-1]
					arr.pop(-1)
				else:
					arr[-1] = arr[-1] - arr[0]
					arr.pop(0)
				count += 1
		print(count)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	c = 0
	if n == 0 or n == 1:
		print(0)
	else:
		while len(l) != 0 and len(l) != 1:
			if l[0] == l[-1]:
				l.pop()
				l.pop(0)
			else:
				c += 1
				if l[0] > l[-1]:
					l[0] = l[0] - l[-1]
					l.pop()
				elif l[0] < l[-1]:
					l[-1] = l[-1] - l[0]
					l.pop(0)
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2 == 0:
		size = n // 2 - 1
	else:
		size = n // 2
	lz = 0
	leftel = a[0]
	rightel = a[n - 1]
	ct = 0
	rz = n - 1
	while len(a) > 1:
		if a[0] == a[-1]:
			del a[0]
			del a[-1]
		else:
			if a[0] > a[-1]:
				a[0] = a[0] - a[-1]
				del a[-1]
			else:
				a[-1] = a[-1] - a[0]
				del a[0]
			ct = ct + 1
	print(ct)


n = int(input())
for i in range(n):
	size = int(input())
	arr = input()
	arr = [int(x) for x in arr.split()]
	count = 0
	f = 0
	l = len(arr) - 1
	while True:
		while arr[f] == arr[l] and f < l:
			f += 1
			l -= 1
		if f >= l:
			break
		if arr[f] < arr[l]:
			arr[l] = arr[l] - arr[f]
			f = f + 1
		else:
			arr[f] = arr[f] - arr[l]
			l = l - 1
		count += 1
	print(count)


t = int(input())
test = 0
while test < t:
	j = 0
	n = int(input())
	count = 0
	arr = list(map(int, input().strip().split()))[:n]
	length = len(arr)
	while length > 1:
		if arr[0] == arr[length - 1]:
			arr.pop(length - 1)
			length = len(arr)
			arr.pop(0)
			length = len(arr)
		elif arr[0] > arr[length - 1]:
			x = arr[length - 1]
			y = arr[0] - x
			arr.pop(0)
			length = len(arr)
			arr.insert(0, y)
			length = len(arr)
			arr.pop(length - 1)
			length = len(arr)
			count += 1
		else:
			y = arr[0]
			x = arr[length - 1] - y
			arr.pop(0)
			length = len(arr)
			arr.pop(length - 1)
			length = len(arr)
			arr.append(x)
			length = len(arr)
			count += 1
	print(count)
	test += 1


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


for i in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	c = 0
	i = 0
	j = x - 1
	while i <= j:
		if l[i] == l[j]:
			i += 1
			j -= 1
			continue
		c += 1
		if l[i] > l[j]:
			k = l[i] - l[j]
			l[i] = k
			j -= 1
		else:
			k = l[j] - l[i]
			l[j] = k
			i += 1
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	r = n - 1
	count = 0
	while i < r:
		x = l[i]
		y = l[r]
		if x < y:
			b = y - x
			l[r] = b
			count += 1
			i = i + 1
		elif x > y:
			a = x - y
			l[i] = a
			count += 1
			r -= 1
		else:
			r = r - 1
			i = i + 1
	print(count)


T = int(input())
for i in range(T):
	n = input()
	str = list(map(int, input().split()))
	c = 0
	while len(str) > 1:
		if str[0] == str[-1]:
			del str[0]
			del str[-1]
		elif str[0] < str[-1]:
			str[-1] = str[-1] - str[0]
			del str[0]
			c += 1
		else:
			str[0] = str[0] - str[-1]
			del str[-1]
			c += 1
	print(c)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	i = 0
	j = n - 1
	while i <= j:
		if arr[i] == arr[j]:
			i += 1
			j -= 1
			continue
		c += 1
		if arr[i] > arr[j]:
			l = arr[i] - arr[j]
			arr[i] = l
			j -= 1
		else:
			l = arr[j] - arr[i]
			arr[j] = l
			i += 1
	print(c)
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	while len(l) > 1:
		if l[0] == l[-1]:
			del l[0]
			del l[-1]
		else:
			if l[0] > l[-1]:
				l[0] = l[0] - l[-1]
				del l[-1]
			else:
				l[-1] = l[-1] - l[0]
				del l[0]
			count += 1
	print(count)
	t -= 1


t = int(input())
while t:
	n = int(input())
	a = [int(x) for x in input().split()]
	l = 0
	h = n - 1
	c = 0
	while l < h:
		if a[l] == a[h]:
			l += 1
			h -= 1
		elif a[l] > a[h]:
			a[l] = a[l] - a[h]
			h -= 1
			c += 1
		else:
			a[h] = a[h] - a[l]
			l += 1
			c += 1
	print(c)
	t -= 1


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	count = 0
	while len(b) > 1:
		if b[0] == b[-1]:
			del b[0]
			del b[-1]
		else:
			if b[0] > b[-1]:
				b[0] = b[0] - b[-1]
				del b[-1]
			else:
				b[-1] = b[-1] - b[0]
				del b[0]
			count += 1
	print(count)


a = int(input())
for i in range(a):
	m = int(input())
	b = list(map(int, input().split()))
	c = []
	d = 0
	while len(b) > 1:
		if b[0] == b[-1]:
			del b[0]
			del b[-1]
		else:
			if b[0] > b[-1]:
				b[0] = b[0] - b[-1]
				del b[-1]
			else:
				b[-1] = b[-1] - b[0]
				del b[0]
			d += 1
	print(d)


testcase = int(input())
while testcase > 0:
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	i = 0
	j = n - 1
	while i <= j:
		if a[i] == a[j]:
			i += 1
			j -= 1
			continue
		c += 1
		if a[i] > a[j]:
			l = a[i] - a[j]
			a[i] = l
			j -= 1
		else:
			l = a[j] - a[i]
			a[j] = l
			i += 1
	print(c)
	testcase -= 1


for _ in range(int(input())):
	n = int(input())
	arr1 = [int(x) for x in input().split()]
	(i, j) = (0, n - 1)
	count = 0
	while i < j:
		a = min(arr1[i], arr1[j])
		b = max(arr1[i], arr1[j])
		if arr1[i] == arr1[j]:
			i += 1
			j -= 1
		elif arr1[i] > arr1[j]:
			arr1[i] -= arr1[j]
			count += 1
			j -= 1
		else:
			arr1[j] -= arr1[i]
			count += 1
			i += 1
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(i, j) = (0, n - 1)
	count = 0
	while i < j:
		a = min(arr[i], arr[j])
		b = max(arr[i], arr[j])
		if arr[i] == arr[j]:
			i += 1
			j -= 1
		elif arr[i] < arr[j]:
			count += 1
			arr[j] -= arr[i]
			i += 1
		else:
			count += 1
			arr[i] -= arr[j]
			j -= 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	r = list(map(int, input().split()))
	i = 0
	j = n - 1
	ct = 0
	while i <= j:
		if r[i] == r[j]:
			i += 1
			j -= 1
		elif r[i] > r[j]:
			r[i] = r[i] - r[j]
			ct += 1
			j -= 1
		else:
			r[j] = r[j] - r[i]
			ct += 1
			i += 1
	print(ct)


testcases = int(input())
for i in range(testcases):
	n = int(input())
	array = list(map(int, input().split()))
	count = 0
	while len(array) > 1:
		if array[0] == array[-1]:
			del array[0]
			del array[-1]
		else:
			if array[0] > array[-1]:
				array[0] = array[0] - array[-1]
				del array[-1]
			else:
				array[-1] = array[-1] - array[0]
				del array[0]
			count += 1
	print(count)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	r = len(a) - 1
	count = 0
	while l < r:
		if a[l] == a[r]:
			l = l + 1
			r = r - 1
		elif a[l] < a[r]:
			a[r] = a[r] - a[l]
			l = l + 1
			count = count + 1
		else:
			a[l] = a[l] - a[r]
			r = r - 1
			count = count + 1
	print(count)


for tc in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	l = 0
	r = len(s) - 1
	c = 0
	while l < r:
		if s[l] < s[r]:
			s[r] -= s[l]
			l += 1
			c += 1
		elif s[l] > s[r]:
			s[l] -= s[r]
			r -= 1
			c += 1
		else:
			l += 1
			r -= 1
	print(c)


n = int(input())

def pal(arr):
	x = 0
	(i, j) = (0, len(arr) - 1)
	while i <= j:
		if arr[i] == arr[j]:
			i += 1
			j -= 1
		elif arr[i] > arr[j]:
			arr[i] -= arr[j]
			j -= 1
			x = x + 1
		else:
			arr[j] -= arr[i]
			i += 1
			x = x + 1
	return x
for i in range(n):
	length = int(input())
	li = list(map(int, input().split()))
	print(pal(li))


t = int(input())
for i in range(t):
	k = int(input())
	arr = list(map(int, input().split()))
	c = 0
	while len(arr) > 1:
		if arr[0] == arr[-1]:
			del arr[0]
			del arr[-1]
		else:
			if arr[0] > arr[-1]:
				arr[0] = arr[0] - arr[-1]
				del arr[-1]
			else:
				arr[-1] = arr[-1] - arr[0]
				del arr[0]
			c += 1
	print(c)


t = int(input())
for i in range(t):
	a = int(input())
	b = list(map(int, input().split()))
	c = 0
	while len(b) > 1:
		if b[0] == b[a - 1]:
			del b[0]
			del b[len(b) - 1]
			a = a - 2
		elif b[0] < b[a - 1]:
			b[a - 1] = b[a - 1] - b[0]
			del b[0]
			a = a - 1
			c = c + 1
		else:
			b[0] = b[0] - b[a - 1]
			del b[a - 1]
			a = a - 1
			c = c + 1
	print(c)


T = int(input())
for _ in range(T):
	N = int(input())
	array = list(map(int, input().split()))
	count = 0
	while len(array) > 1:
		if array[0] == array[-1]:
			del array[0]
			del array[-1]
		else:
			if array[0] > array[-1]:
				array[0] = array[0] - array[-1]
				del array[-1]
			else:
				array[-1] = array[-1] - array[0]
				del array[0]
			count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	r = n - 1
	s = 0
	while True:
		if a[l] < a[r]:
			a[r] -= a[l]
			l += 1
			s += 1
		elif a[r] < a[l]:
			a[l] -= a[r]
			r -= 1
			s += 1
		else:
			l += 1
			r -= 1
		if l >= r:
			break
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	e = n - 1
	ans = 0
	while s < e:
		if a[s] == a[e]:
			s += 1
			e -= 1
		elif a[s] > a[e]:
			ans += 1
			a[s] -= a[e]
			e -= 1
		else:
			ans += 1
			a[e] -= a[s]
			s += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	z = list(map(int, input().split()))
	ans = 0
	j = 0
	k = n - 1
	while j < k:
		if z[j] == z[k]:
			j += 1
			k -= 1
		elif z[j] > z[k]:
			ans += 1
			z[j] = z[j] - z[k]
			k -= 1
		else:
			ans += 1
			z[k] -= z[j]
			j += 1
	print(ans)


from collections import deque
for i in range(int(input())):
	n = int(input())
	a = deque(map(int, input().split()))
	ans = 0

	def pops():
		a.pop()
		a.popleft()
	while len(a) >= 2:
		if a[0] == a[-1]:
			pops()
		elif a[0] < a[-1]:
			ans = ans + 1
			s = a[-1] - a[0]
			pops()
			a.append(s)
		elif a[0] > a[-1]:
			ans = ans + 1
			s = a[0] - a[-1]
			pops()
			a.appendleft(s)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))[:n]
	count = 0
	for i in range(len(A)):
		N = len(A) - 1
		temp = 0
		if i == N - i:
			break
		if A[i] < A[N - i]:
			temp = A[N - i]
			A[N - i] = A[i]
			A.insert(N - i, temp - A[i])
			count += 1
		elif A[i] > A[N - i]:
			temp = A[i]
			A[i] = A[N - i]
			A.insert(i + 1, temp - A[N - i])
			count += 1
	print(count)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	while len(l) > 1:
		if l[0] == l[-1]:
			del l[0]
			del l[-1]
		elif l[0] < l[-1]:
			c += 1
			x = l[-1] - l[0]
			del l[0]
			del l[-1]
			l.append(x)
		elif l[0] > l[-1]:
			c += 1
			y = l[0] - l[-1]
			del l[0]
			del l[-1]
			l.insert(0, y)
	print(c)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	while len(a) > 1:
		if a[0] == a[-1]:
			del a[0]
			del a[-1]
		elif a[0] > a[-1]:
			a[0] = a[0] - a[-1]
			del a[-1]
			c = c + 1
		else:
			a[-1] = a[-1] - a[0]
			del a[0]
			c = c + 1
	print(c)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	r = n - 1
	c = 0
	while l < r:
		if a[l] == a[r]:
			l += 1
			r -= 1
		elif a[l] < a[r]:
			a[r] = a[r] - a[l]
			l += 1
			c += 1
		else:
			a[l] = a[l] - a[r]
			r -= 1
			c += 1
	print(c)


def palindrom(a):
	count = 0
	while len(a) > 1:
		if a[0] == a[-1]:
			del a[0]
			del a[-1]
		else:
			if a[0] > a[-1]:
				a[0] -= a[-1]
				del a[-1]
			else:
				a[-1] -= a[0]
				del a[0]
			count += 1
	print(count)
for i in range(int(input())):
	n = int(input())
	num = list(map(int, input().split(' ')))
	palindrom(num)


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


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


testcase = int(input())
while testcase:
	n = int(input())
	arr = list(map(int, input().split()))
	low = 0
	high = n - 1
	count = 0
	while low < high:
		if arr[low] == arr[high]:
			low += 1
			high -= 1
		elif arr[low] > arr[high]:
			arr[low] = arr[low] - arr[high]
			high -= 1
			count += 1
		else:
			arr[high] = arr[high] - arr[low]
			low += 1
			count += 1
	print(count)
	testcase -= 1


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