You are given an array $a$ consisting of $n$ integers. Indices of the array start from zero (i. e. the first element is $a_0$, the second one is $a_1$, and so on).

You can reverse at most one subarray (continuous subsegment) of this array. Recall that the subarray of $a$ with borders $l$ and $r$ is $a[l; r] = a_l, a_{l + 1}, \dots, a_{r}$.

Your task is to reverse such a subarray that the sum of elements on even positions of the resulting array is maximized (i. e. the sum of elements $a_0, a_2, \dots, a_{2k}$ for integer $k = \lfloor\frac{n-1}{2}\rfloor$ should be maximum possible).

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of $a$. The second line of the test case contains $n$ integers $a_0, a_1, \dots, a_{n-1}$ ($1 \le a_i \le 10^9$), where $a_i$ is the $i$-th element of $a$.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer on the separate line — the maximum possible sum of elements on even positions after reversing at most one subarray (continuous subsegment) of $a$.


-----Example-----
Input
4
8
1 7 3 4 7 6 2 9
5
1 2 1 2 1
10
7 8 4 5 7 6 8 9 7 3
4
3 1 2 1

Output
26
5
37
5

Difficulty: interview

Starter code:

Solutions:
def subsolve(a):
    c = 0
    m = 0
    for i in a:
        c += i
        if c < 0:
            c = 0
        m = max(m, c)
    return m
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    s = 0
    for i in range(0, n, 2):
        s += a[i]
    u = subsolve([a[i] - a[i - 1] for i in range(1, n, 2)])
    v = subsolve([a[i - 1] - a[i] for i in range(2, n, 2)])
    print(max(u, v) + s)
t = int(input())
for _ in range(t):
    solve()

def max_sub(a):
    total_max = 0
    cur_max = 0
    for v in a:
        cur_max += v
        cur_max = max(cur_max, 0)
        total_max = max(total_max, cur_max)
    return total_max

t = int(input())

for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    
    a1 = list(a[::2])
    a2 = list(a[1::2])
    
    d1 = list(y-x for x, y in zip(a1, a2))
    d2 = list(y-x for x, y in zip(a1[1:], a2))
    
    print(sum(a1) + max(max_sub(d1), max_sub(d2)))
    


import sys
input = sys.stdin.readline


t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))

    ru = [0] * (n + 1)
    ans = 0
    for i in range(n):
        if i % 2 == 0:
            ans += a[i]
            ru[i + 1] = ru[i] - a[i]
        else:
            ru[i + 1] = ru[i] + a[i]

    li1 = [0]
    li2 = [0]
    for i in range(n):
        if i % 2 == 0:
            li1.append(ru[i + 1])
        else:
            li2.append(ru[i + 1])

    add = 0
    min_val = 0
    for val in li1:
        add = max(val - min_val, add)
        min_val = min(min_val, val)

    min_val = 0
    for val in li2:
        add = max(val - min_val, add)
        min_val = min(min_val, val)

    print(ans + add)

from sys import exit,stdin,stderr
def rl():
    return [int(w) for w in stdin.readline().split()]

def maxsum(b):
    cur = r = 0
    for x in b:
        cur += x
        if cur < 0:
            cur = 0
        elif cur > r:
            r = cur
    return r

T, = rl()
for _ in range(T):
    n, = rl()
    a = rl()
    print((sum(a[::2]) + max(maxsum(b) for b in[
        [a[i] - a[i-1] for i in range(1, n, 2)],
        [a[i-1] - a[i] for i in range(2, n, 2)],
    ])))



tt = int(input())

for loop in range(tt):

    n = int(input())
    a = list(map(int,input().split()))

    e = [0]
    o = [0]

    for i in range(n):
        if i % 2 == 0:
            e.append(e[-1] + a[i])
            o.append(o[-1])
        else:
            e.append(e[-1])
            o.append(o[-1] + a[i])

    eo = []
    for i in range(n+1):
        eo.append(o[i]-e[i])

    nmin = float("inf")
    ans = 0
    for i in range(0,n+1,2):
        ans = max(ans , eo[i]-nmin)
        nmin = min(nmin,eo[i])

    nmin = float("inf")
    for i in range(1,n+1,2):
        ans = max(ans , eo[i]-nmin)
        nmin = min(nmin,eo[i])

    ori = 0
    for i in range(0,n,2):
        ori += a[i]

    print(ori + ans)


# f = open('test.py')
# def input():
# 	return f.readline().replace('\n','')

# import heapq
# from collections import defaultdict
def read_list():
	return list(map(int,input().strip().split(' ')))
def print_list(l):
	print(' '.join(map(str,l)))

N = int(input())
for _ in range(N):
	n = int(input())
	a = read_list()
	res = 0
	tmp = 0
	s = 0
	for i in range(1,n,2):
		s+=a[i]-a[i-1]
		res = max(res,s-tmp)
		tmp = min(tmp,s)
	tmp = 0
	s = 0
	for i in range(1,n-1,2):
		s+=a[i]-a[i+1]
		res = max(res,s-tmp)
		tmp = min(tmp,s)
	print(sum(a[::2])+res)







			


import math
import sys
from itertools import permutations
input = sys.stdin.readline

t=int(input())
for i in range(t):
    n=int(input())
    arr=list(map(int,input().split()))

    ans=0
    for j in range(n):
        if j%2==0:
            ans+=arr[j]
    
    arr1=[]
    for j in range(1,n,2):
        arr1.append(arr[j]-arr[j-1])
    
    msf=0
    meh=0
    for j in range(len(arr1)):
        meh+=arr1[j]
        if msf<=meh:
            msf=meh
        if meh<0:
            meh=0
    cur1=ans+msf

    arr2=[]
    for j in range(2,n,2):
        arr2.append(arr[j-1]-arr[j])

    msf=0
    meh=0
    for j in range(len(arr2)):
        meh+=arr2[j]
        if msf<=meh:
            msf=meh
        if meh<0:
            meh=0
    cur2=ans+msf
    # print(cur1,cur2)
    print(max(cur1,cur2))