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: interview

Starter code:

Solutions:
# cook your dish here
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
    #print(prefix_odd,prefix_even)
    prefix_sum=[0]*n
    s=0
    for i in range(n):
        s+=lst[i]
        prefix_sum[i]=s
    #print(prefix_sum)
    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
    #print(dict)
    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
                #print(index1,index2)
                if i%2==0:
                    val=prefix_even[index2]-prefix_even[index1]-1
                    #print(val)
                    if val%2==0:
                        temp_sum=prefix_sum[index2]-prefix_sum[index1]-i
                        #print(temp_sum)
                        if temp_sum>max_sum:
                            max_sum=temp_sum
                else:
                    val=prefix_odd[index2]-prefix_odd[index1]-1
                    #print(val)
                    if val%2!=0:
                        temp_sum=prefix_sum[index2]-prefix_sum[index1]-i
                        #print(temp_sum)
                        if temp_sum>max_sum:
                            max_sum=temp_sum

    '''max_sum=-1
                for i in range(n):
                    if count[lst[i]]>1:
                        index2=dict[lst[i]]
                        index1=i
                        print(index1,index2)
                        if lst[i]%2==0:
                            val=prefix_even[index2]-prefix_even[index1]-1
                            print(val)
                            if val%2==0:
                                temp_sum=prefix_sum[index2]-prefix_sum[index1]-lst[i]
                                print(temp_sum)
                                if temp_sum>max_sum:
                                    max_sum=temp_sum
                        else:
                            val=prefix_odd[index2]-prefix_odd[index1]-1
                            print(val)
                            if val%2!=0:
                                temp_sum=prefix_sum[index2]-prefix_sum[index1]-lst[i]
                                print(temp_sum)
                                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)

# cook your dish here
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])
            else:
                if 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
                else:
                    if (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)
        else:
            if 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)
        else:
            if 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)

# cook your dish here
# JUST FIND IT
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]
        else:
            if 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
            # print(tmp_sum)
            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")

# sys.stdout=open("CP2/output.txt",'w')
# sys.stdin=open("CP2/input.txt",'r')

# mod=pow(10,9)+7
t=int(input())
for i in range(t):
	n=int(input())
	a=list(map(int,input().split()))
	even=[0]*n
	# odd=[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]]])
			else:
				if (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)

# cook your dish here
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]
  ## print(even)
   ##print(odd)
   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]
               ##print(even[z])
               if y==0:

                   ##print(even[z],i)
                   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)
               ##print(maxi,i,"hi")

           if x%2==1:
               y = d[a[i]][0]
               z = d[a[i]][1]
               if y==0:
                  ## print(odd[z])
                   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)






#dt = {} for i in x: dt[i] = dt.get(i,0)+1
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
    #print(x)
    #print(pre)
    #print(dt)
    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)
            else:
                if ((b-1-a+1+1)-ct)%2 == 0:
                    ans = max(ans,t)
    print(ans)