Given an array $A$ of length $N$.
We have to find the $maximum$ sum of elements of the subarray between $two$ nearest occurrences of $same$ elements (excluding both).
If both the elements are $even$ then the total number of $even$ elements in that subarray should be $even$ then and then only we consider that subarray and if both the elements are $odd$ then the total number of $odd$ element in that subarray should be $odd$ then and then only we consider that subarray.
If the condition never matches print $0$.

-----Input:-----
- First line contains $T$, number of test cases. Then the test cases follow.
- Each testcase consists of two lines: 
The first line has $N$ : number of elements in the array and second-line has $N$ space separated integers: elements of the array.

-----Output:-----
- For each test case, output in a single line $maximum$ sum.

-----Constraints-----
- $1 \leq T \leq 10$
- $3 \leq N \leq 2*10^5$
- $1 \leq A[i] \leq 10^8$
$NOTE $: Use of Fast Input Output is recommended.

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

-----Sample Output:-----
7

-----EXPLANATION:-----
The maximum sum is 7, between 1 at  1st position and 1 at 5th position i.e sum of 2,3,2

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from sys import stdin, stdout
from collections import defaultdict
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	lst = list(map(int, stdin.readline().split()))
	prefix_odd = [0] * n
	prefix_even = [0] * n
	odd_val = 0
	even_val = 0
	for i in range(n):
		if lst[i] % 2 == 0:
			even_val += 1
		else:
			odd_val += 1
		prefix_even[i] = even_val
		prefix_odd[i] = odd_val
	prefix_sum = [0] * n
	s = 0
	for i in range(n):
		s += lst[i]
		prefix_sum[i] = s
	dict = {}
	count = {}
	for i in range(n):
		if lst[i] not in dict:
			dict[lst[i]] = i
			count[lst[i]] = 1
		else:
			dict[lst[i]] = i
			count[lst[i]] += 1
	graph = defaultdict(list)
	for i in range(n):
		graph[lst[i]].append(i)
	max_sum = 0
	for i in graph:
		if len(graph[i]) > 1:
			prev = graph[i][0]
			for j in range(1, len(graph[i])):
				index2 = graph[i][j]
				index1 = prev
				prev = index2
				if i % 2 == 0:
					val = prefix_even[index2] - prefix_even[index1] - 1
					if val % 2 == 0:
						temp_sum = prefix_sum[index2] - prefix_sum[index1] - i
						if temp_sum > max_sum:
							max_sum = temp_sum
				else:
					val = prefix_odd[index2] - prefix_odd[index1] - 1
					if val % 2 != 0:
						temp_sum = prefix_sum[index2] - prefix_sum[index1] - i
						if temp_sum > max_sum:
							max_sum = temp_sum
	stdout.write(str(max_sum) + '\n')


from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr3 = list((1 if i % 2 else 0 for i in arr))
	for i in range(1, n):
		arr3[i] += arr3[i - 1]
	arr2 = [arr[0]]
	for i in range(1, n):
		arr2.append(arr2[-1] + arr[i])
	ans = 0
	d = defaultdict(list)
	for i in range(n):
		if d[arr[i]] == []:
			d[arr[i]].append(i)
		else:
			cnt1 = arr3[i - 1] - arr3[d[arr[i]][0]]
			if arr[i] % 2 and cnt1 % 2 or (arr[i] % 2 == 0 and (i - 1 - d[arr[i]][0] - cnt1) % 2 == 0):
				ans = max(ans, arr2[i - 1] - arr2[d[arr[i]][0]])
			d[arr[i]] = [i]
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(odd, even, pref) = ([0], [0], [0])
	d = dict()
	ans = 0
	for i in range(n):
		if arr[i] & 1:
			odd.append(odd[-1] + 1)
			even.append(even[-1])
		else:
			odd.append(odd[-1])
			even.append(even[-1] + 1)
		pref.append(pref[-1] + arr[i])
		if arr[i] in d:
			if arr[i] & 1:
				if abs(odd[i + 1] - odd[d[arr[i]]] - 2) & 1:
					ans = max(ans, pref[i + 1] - pref[d[arr[i]]] - 2 * arr[i])
			elif abs(even[i + 1] - even[d[arr[i]]] - 2) % 2 == 0:
				ans = max(ans, pref[i + 1] - pref[d[arr[i]]] - 2 * arr[i])
		d[arr[i]] = i
	print(ans)


t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	li = list(map(int, input().split()))
	odd = [0] * n
	eve = [0] * n
	su = [0] * n
	ans = 0
	x = 0
	o = 0
	e = 0
	dic = {}
	for i in range(n):
		x += li[i]
		su[i] = x
		if li[i] not in dic:
			dic[li[i]] = []
			dic[li[i]].append(i)
		else:
			dic[li[i]].append(i)
		if li[i] % 2 == 0:
			e += 1
		else:
			o += 1
		eve[i] = e
		odd[i] = o
	for j in dic:
		if len(dic[j]) == 1:
			continue
		else:
			for o in range(0, len(dic[j]) - 1):
				fir = dic[j][o]
				sec = dic[j][o + 1]
				if j % 2 == 0:
					if (eve[sec - 1] - eve[fir]) % 2 == 0:
						jk = su[sec - 1] - su[fir]
						if jk > ans:
							ans = jk
				elif (odd[sec - 1] - odd[fir]) % 2 != 0 and (odd[sec - 1] != 0 or odd[fir] != 0):
					jk = su[sec - 1] - su[fir]
					if jk > ans:
						ans = jk
	print(ans)


from collections import *
for _ in range(int(input())):
	n = int(input())
	l = [*map(int, input().split())]
	ans = 0
	ind = defaultdict(list)
	even = []
	odd = []
	for i in range(n):
		ind[l[i]].append(i)
		if l[i] % 2 == 0:
			if not even:
				even.append(1)
			else:
				even.append(even[-1] + 1)
		elif not even:
			even.append(0)
		else:
			even.append(even[-1])
		if l[i] % 2 == 1:
			if not odd:
				odd.append(1)
			else:
				odd.append(odd[-1] + 1)
		elif not odd:
			odd.append(0)
		else:
			odd.append(odd[-1])
	pre_sum = [l[0]]
	for i in range(1, n):
		pre_sum.append(pre_sum[-1] + l[i])
	for i in ind:
		x = len(ind[i])
		if x > 1:
			for j in range(x - 1):
				if i % 2 == 0:
					if ind[i][j] > 0 and even[ind[i][j] + 1] != even[ind[i][j]] and ((even[ind[i][j + 1] - 1] - even[ind[i][j] + 1] + 1) % 2 == 0):
						ans = max(ans, pre_sum[ind[i][j + 1] - 1] - pre_sum[ind[i][j]])
					elif ind[i][j] == 0 and even[ind[i][j] + 1] != even[ind[i][j]] and ((even[ind[i][j + 1] - 1] - even[ind[i][j] + 1] + 1) % 2 == 0):
						ans = max(ans, pre_sum[ind[i][j + 1] - 1] - pre_sum[ind[i][j]])
					elif ind[i][j] == 0 and even[ind[i][j] + 1] == even[ind[i][j]] and ((even[ind[i][j + 1] - 1] - even[ind[i][j] + 1]) % 2 == 0):
						ans = max(ans, pre_sum[ind[i][j + 1] - 1] - pre_sum[ind[i][j]])
					elif ind[i][j] > 0 and even[ind[i][j] + 1] == even[ind[i][j]] and ((even[ind[i][j + 1] - 1] - even[ind[i][j] + 1]) % 2 == 0):
						ans = max(ans, pre_sum[ind[i][j + 1] - 1] - pre_sum[ind[i][j]])
				if i % 2 == 1:
					if ind[i][j] > 0 and odd[ind[i][j] + 1] != odd[ind[i][j]] and ((odd[ind[i][j + 1] - 1] - odd[ind[i][j] + 1] + 1) % 2 == 1):
						ans = max(ans, pre_sum[ind[i][j + 1] - 1] - pre_sum[ind[i][j]])
					elif ind[i][j] == 0 and odd[ind[i][j] + 1] == odd[ind[i][j]] and ((odd[ind[i][j + 1] - 1] - odd[ind[i][j] + 1]) % 2 == 1):
						ans = max(ans, pre_sum[ind[i][j + 1] - 1] - pre_sum[ind[i][j]])
					elif ind[i][j] == 0 and odd[ind[i][j] + 1] != odd[ind[i][j]] and ((odd[ind[i][j + 1] - 1] - odd[ind[i][j] + 1] + 1) % 2 == 1):
						ans = max(ans, pre_sum[ind[i][j + 1] - 1] - pre_sum[ind[i][j]])
					elif ind[i][j] > 0 and odd[ind[i][j] + 1] == odd[ind[i][j]] and ((odd[ind[i][j + 1] - 1] - odd[ind[i][j] + 1]) % 2 == 1):
						ans = max(ans, pre_sum[ind[i][j + 1] - 1] - pre_sum[ind[i][j]])
	print(ans)


def splitting(arr):
	if len(arr) == len(set(arr)):
		return 0
	ev_od = {}
	occur = {}
	ans = 0
	for (i, n) in enumerate(arr):
		if i == 0:
			ev_od[i] = [0, 0, 0]
		elif arr[i - 1] & 1 == 1:
			ev_od[i] = [ev_od[i - 1][0], ev_od[i - 1][1] + 1, ev_od[i - 1][2] + arr[i - 1]]
		else:
			ev_od[i] = [ev_od[i - 1][0] + 1, ev_od[i - 1][1], ev_od[i - 1][2] + arr[i - 1]]
		if n in occur:
			if n & 1 == 1:
				num_of_odd = ev_od[i][1] - ev_od[occur[n]][1] - 1
				if num_of_odd & 1 == 1:
					tmp_sum = ev_od[i][2] - ev_od[occur[n]][2] - n
				else:
					tmp_sum = 0
			else:
				num_of_even = ev_od[i][0] - ev_od[occur[n]][0] - 1
				if num_of_even & 1 == 0:
					tmp_sum = ev_od[i][2] - ev_od[occur[n]][2] - n
				else:
					tmp_sum = 0
			ans = max(ans, tmp_sum)
		occur[n] = i
	return ans
try:
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		print(splitting(arr))
except:
	pass


from sys import stdin, stdout
from itertools import accumulate

def Oddnos(l, r):
	smm = od[r - 1] - od[l]
	return smm & 1

def evennos(l, r):
	tot = r - l - 1
	smm = od[r - 1] - od[l]
	return tot - smm & 1 == 0

def getSum(l, r):
	return ps[r] - (ps[l - 1] if l >= 1 else 0)
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	od = list(accumulate([x & 1 for x in a]))
	ps = list(accumulate(a))
	d = {}
	mx = 0
	for i in range(n):
		if a[i] in d:
			prev = d[a[i]]
			if a[i] & 1 and Oddnos(prev, i):
				mx = max(mx, getSum(prev, i) - 2 * a[i])
			elif a[i] & 1 == 0 and evennos(prev, i):
				mx = max(mx, getSum(prev, i) - 2 * a[i])
		d[a[i]] = i
	print(mx)


import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	even = [0] * n
	ans = 0
	pre = [0] * n
	pre[0] = a[0]
	d = {a[0]: 0}
	if a[0] % 2 == 0:
		even[0] = 1
	for j in range(1, n):
		s = d.get(a[j], -1)
		if s == -1:
			d[a[j]] = j
		else:
			if a[j] & 1:
				if pre[j - 1] - pre[d[a[j]]] & 1:
					ans = max(ans, pre[j - 1] - pre[d[a[j]]])
			elif (even[j - 1] - even[d[a[j]]]) % 2 == 0:
				ans = max(ans, pre[j - 1] - pre[d[a[j]]])
			d[a[j]] = j
		pre[j] = pre[j - 1] + a[j]
		even[j] = even[j - 1]
		if a[j] % 2 == 0:
			even[j] += 1
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	maxi = -1
	d = defaultdict(list)
	n = int(input())
	a = list(map(int, input().split()))
	even = [0] * n
	odd = [0] * n
	pref = [0] * n
	pref[0] = a[0]
	if a[0] % 2 == 0:
		even[0] = 1
	if a[0] % 2 == 1:
		odd[0] = 1
	d[a[0]].append(0)
	for i in range(1, n):
		d[a[i]].append(i)
		if a[i] % 2 == 0:
			even[i] = even[i - 1] + 1
			odd[i] = odd[i - 1]
		if a[i] % 2 == 1:
			odd[i] = odd[i - 1] + 1
			even[i] = even[i - 1]
		pref[i] = pref[i - 1] + a[i]
	for i in range(n):
		x = a[i]
		if len(d[a[i]]) >= 2:
			if x % 2 == 0:
				y = d[a[i]][0]
				z = d[a[i]][1]
				if y == 0:
					if even[z] % 2 == 0:
						maxi = max(maxi, pref[z] - pref[y] - x)
					continue
				if (even[z] - even[y - 1]) % 2 == 0:
					maxi = max(maxi, pref[z] - pref[y] - x)
			if x % 2 == 1:
				y = d[a[i]][0]
				z = d[a[i]][1]
				if y == 0:
					if odd[z] % 2 == 1:
						maxi = max(maxi, pref[z] - pref[y] - x)
					continue
				if (odd[z] - odd[y - 1]) % 2 == 1:
					maxi = max(maxi, pref[z] - pref[y] - x)
		d[a[i]].pop(0)
	if maxi == -1:
		print(0)
		continue
	print(maxi)


import sys
input = sys.stdin.readline
(inp, ip) = (lambda : int(input()), lambda : [int(w) for w in input().split()])
for _ in range(inp()):
	n = inp()
	x = ip()
	par = [i % 2 for i in x]
	pre = [0] * (n + 1)
	prepar = [0] * (n + 1)
	dt = {}
	for i in range(n):
		pre[i + 1] = pre[i] + x[i]
		prepar[i + 1] = prepar[i] + par[i]
		t = dt.get(x[i], [])
		t.append(i)
		dt[x[i]] = t
	ans = 0
	for i in range(n):
		if len(dt[x[i]]) > 1:
			(a, b) = dt[x[i]][:2]
			dt[x[i]] = dt[x[i]][1:]
			if a == b:
				continue
			t = pre[b] - pre[a + 1]
			ct = prepar[b] - pre[a + 1]
			if x[i] % 2:
				if ct % 2:
					ans = max(ans, t)
			elif (b - 1 - a + 1 + 1 - ct) % 2 == 0:
				ans = max(ans, t)
	print(ans)