Danny, the local Math Maniac, is fascinated by circles, Omkar's most recent creation. Help him solve this circle problem!

You are given $n$ nonnegative integers $a_1, a_2, \dots, a_n$ arranged in a circle, where $n$ must be odd (ie. $n-1$ is divisible by $2$). Formally, for all $i$ such that $2 \leq i \leq n$, the elements $a_{i - 1}$ and $a_i$ are considered to be adjacent, and $a_n$ and $a_1$ are also considered to be adjacent. In one operation, you pick a number on the circle, replace it with the sum of the two elements adjacent to it, and then delete the two adjacent elements from the circle. This is repeated until only one number remains in the circle, which we call the circular value.

Help Danny find the maximum possible circular value after some sequences of operations. 


-----Input-----

The first line contains one odd integer $n$ ($1 \leq n < 2 \cdot 10^5$, $n$ is odd)  — the initial size of the circle.

The second line contains $n$ integers $a_{1},a_{2},\dots,a_{n}$ ($0 \leq a_{i} \leq 10^9$)  — the initial numbers in the circle.


-----Output-----

Output the maximum possible circular value after applying some sequence of operations to the given circle.


-----Examples-----
Input
3
7 10 2

Output
17

Input
1
4

Output
4



-----Note-----

For the first test case, here's how a circular value of $17$ is obtained:

Pick the number at index $3$. The sum of adjacent elements equals $17$. Delete $7$ and $10$ from the circle and replace $2$ with $17$.

Note that the answer may not fit in a $32$-bit integer.

Difficulty: interview

Starter code:

Solutions:
x = int(input())
y = list(map(int, input().split(' ')))
bad = x//2
s = 0
t=0
y = y + y
for i in range(bad):
    s += y[2*i]
    # print("adding {} to s".format(2*i))
    t += y[2*i+1]
    # print("adding {} to t".format(2*i+1))

mini = min(s, t)
for i in range(bad):
    s -= y[2*i]
    # print("subing {} to s".format(2*i))

    s += y[2*(bad+i)]
    # print("adding {} to s".format(2*(bad+i)))

    t -= y[2*i+1]
    # print("sub {} to t".format(2*i+1))

    t += y[2*(bad+i)+1]
    # print("adding {} to t".format(2*(bad+i)+1))

    mini = min(mini, min(s, t))
print(sum(y)//2-mini)

from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    n = ri()
    A = rl()
    odd_total = 0
    even_total = 0
    for i in range(n):
        if i % 2 == 0:
            even_total += A[i]
        else:
            odd_total += A[i]

    best = 0
    even_before = 0
    odd_before = 0
    even_after = even_total
    odd_after = odd_total
    for i in range(n):
        if i % 2 == 0:
            even_after -= A[i]
            even_before += A[i]
            candidate = even_before + odd_after
        else:
            odd_after -= A[i]
            odd_before += A[i]
            candidate = odd_before + even_after
        best = max(best, candidate)

    print (best)





mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()



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

l1 = [0]
l2 = [0]
r1 = [0]
r2 = [0]

for i in range(n):

    if i % 2 == 0:
        l1.append(l1[-1] + a[i])
        l2.append(l2[-1])
        r1.append(r1[-1])
        r2.append(r2[-1] + a[n-1-i])

    else:
        l1.append(l1[-1])
        l2.append(l2[-1] + a[i])
        r1.append(r1[-1] + a[n-1-i])
        r2.append(r2[-1])

ans = 0
for i in range(n+1):
    ans = max(ans , l1[i]+r1[n-i] , l2[i]+r2[n-i])
print (ans)


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

pref_odd = [0]
curr = 0
for i in range(n):
    if i % 2 == 1:
        curr += l[i]
    pref_odd.append(curr)

pref_even = [0]
curr = 0
for i in range(n):
    if i % 2 == 0:
        curr += l[i]
    pref_even.append(curr)

best = 0
for i in range(n):
    o1 = pref_even[i] + (pref_odd[-1] - pref_odd[i+1])
    o2 = pref_odd[i] + (pref_even[-1] - pref_even[i+1])
    best = max(best,max(o1,o2)+l[i])
print(best)


def getsum(a, b, pref):
    if b < a:
        b += n
    return pref[b] - pref[a]


for _ in range(1):
    # for _ in range(int(input())):
    # a, b = map(int, input().split())
    n = int(input())
    arr = list(map(int, input().split()))
    # s = input()
    pref0 = [0] * (len(arr) + 1)
    pref1 = [0] * (len(arr) + 1)
    for i in range(1, len(pref0)):
        pref0[i] = pref0[i - 1]
        pref1[i] = pref1[i - 1]
        if i % 2 == 1:
            pref0[i] += arr[i - 1]
        else:
            pref1[i] += arr[i - 1]
    mx = pref0[-1]
    s = sum(arr)
    for i in range(n - 1):
        if i % 2 == 0:
            x = pref0[i + 1] + (s - pref0[-1] - pref1[i + 1])
        else:
            x = pref1[i + 1] + (s - pref1[-1] - pref0[i + 1])
        mx = max(mx, x)
    print(mx)

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n//2):
  ans+=a[2*i]
ans+=a[n-1]
pointer=n-1
pointer2=0
maxans=ans
for i in range(n):
  ans-=a[pointer2]
  pointer2=(pointer2+2)%n
  ans+=a[(pointer+2)%n]
  pointer=(pointer+2)%n
  maxans=max(ans,maxans)
print(maxans)

import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(lst):  # fix inputs here
    console("----- solving ------")

    arr = []
    arr.extend(lst[::2])
    arr.extend(lst[1::2])
    arr.extend(lst[::2])
    arr.extend(lst[1::2])

    psum = []
    ps = 0
    for i in arr:
        ps += i
        psum.append(ps)
    
    res = 0
    sub_length = (len(lst)+1)//2
    # console(psum, sub_length)
    for i in range(len(lst)):
        res = max(res, psum[i+sub_length] - psum[i])

    # return a string (i.e. not a list or matrix)
    return res


def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
# sys.stdin.readlines()

# for case_num in range(int(input())):
    # read line as a string
    # strr = input()

    # read line as an integer
_ = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    # grid = []
    # for _ in range(nrows):
    #     grid.append(list(map(int,input().split())))

res = solve(lst)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
print(res)


y=lambda x:print(x)or quit()
n=int(input())
p=list(map(int,input().split()))
if n<2:y(p[0])
if n<4:y(sum(p)-min(p))
s=[p[-1],p[-2]]
r=[p[0],p[1]]
for i in range(2,n):
    r.append(r[-2]+p[i])
    s.append(s[-2]+p[-i-1])
s=s[::-1]
m=r[-1]+r[-2]
for i in range(n-3):m=min(m,r[i]+s[i+3])
m=min([m,r[n-3],s[1],s[2]])
y(r[-1]+r[-2]-m)

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
a = [int(item) for item in input().split()]
total = sum(a)
if n == 1:
    print(total)
    return
val = sum(a[::2])
a.append(a[0])

ans = 0
for a0, a1 in zip(a, a[1:]):
    val = total - val + a0
    ans = max(ans, val)
print(ans)

n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
    print(a[0])
else:
    b = a + a
    k = (n+1)//2
    s = 0
    for j in range(0, 2*k, 2):
        s += b[j]
    M = s
    left = 0
    while left + 2*k < 2*n:
        s -= b[left]
        s += b[left + 2*k]
        M = max(s, M)
        left += 2
    s = 0
    for j in range(1, 2*k+1, 2):
        s += b[j]
    M = max(s, M)
    left = 1
    while left + 2*k < 2*n:
        s -= b[left]
        s += b[left + 2*k]
        M = max(s, M)
        left += 2
    print(M)

N = int(input())
A = list(map(int,input().split()))
cumev = [0]
cumod = [0]
for i,a in enumerate(A):
    cumev.append(cumev[-1] + (a if i%2==0 else 0))
    cumod.append(cumod[-1] + (a if i%2 else 0))

ans = cumev[-1]
for i,(e,o) in enumerate(zip(cumev,cumod)):
    if i%2:
        tmp = e + cumod[-1] - o
    else:
        tmp = o + cumev[-1] - e
    ans = max(ans,tmp)
print(ans)


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve1(a):
	n = len(a)
	
def solve():
	n = mint()
	a = list(mints())
	if n == 1:
		print(a[0])
		return
	a += a
	#print(a)
	b = [0]*(2*n)
	b[0] = a[0]
	b[1] = a[1]
	for i in range(2,len(b)):
		b[i] = b[i-2]+a[i]
	r = min(b[n-3],b[n-3+1])
	#print(n-3)
	#print(b)
	for j in range(n-3+2,len(b)):
		#print(j,j-(n-3)-2,b[j]-b[j-(n-3)-2])
		r = min(r, b[j]-b[j-(n-3)-2])
	print(sum(a)//2-r)
#for i in range(mint()):
solve()

n=int(input())
a=list(map(int,input().split()))
a=[a[i%n] for i in range(0,2*n,2)]
s1=sum(a[:(n+1)//2])
sx=s1
for i in range(1,n):
	s1+=a[(i+(n-1)//2)%n]-a[i-1]
	sx=max(sx,s1)
print(sx)

n = int(input())
a = list(map(int, input().split()))
ans = 0
cnt = 0
for i in range(0, n, 2):
    cnt += a[i]
ans = cnt
j = 0
for i in range(n):
    cnt -= a[j % n]
    cnt += a[(j + 1) % n]
    ans = max(cnt, ans)
    j += 2
print(ans)

n = int(input())
l = list(map(int,input().split()))
s = sum(l)
x = 0
k = n//2
for i in range(k):x+=l[i*2]
minx = x
for i in range(n-1):
    x-=l[(i*2)%n]
    x+=l[((k+i)*2)%n]
    minx = min(minx,x)
print(s-minx)

import sys
INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br


"""
Facts and Data representation
Constructive? Top bottom up down
"""
def find(x):
  ans = []
  for i in range(1, int(x ** 0.5) + 1):
    if x % i:
      continue
    ans.append(i)
    ans.append(x // i)
  return ans

def solve():
  n, = I()
  a = I() * 2
  ans = sum(a) // 2
  mn = INF
  odd = even = 0
  for i in range(n - 1):
    if i % 2:
      odd += a[i]
    else:
      even += a[i]
  mn = min(odd, even)
  back = n - 1
  for i in range(n - 1, 2 * n):
    if i % 2:
      odd += a[i]
      odd -= a[i - back]
    else:
      even += a[i]
      even -= a[i - back]
    mn = min(mn, odd, even)
  print(ans - mn)


solve()

import math
import sys
input = sys.stdin.readline
t = 1
for cs in range(t):
    n = int(input())
    a = [int(_) for _ in input().split()]
    if n == 1:
        print(a[0])
        continue
    pre = [0] * n
    suf = [0] * n
    for i in range(n):
        if i >= 2:
            pre[i] = pre[i - 2] + a[i]
        else:
            pre[i] = a[i]
    for i in range(n - 1, -1, -1):
        if i + 2 < n:
            suf[i] = suf[i + 2] + a[i]
        else:
            suf[i] = a[i]
    ans = max(pre[0], pre[1])
    for i in range(n):
        if i > 0:
            ans = max(ans, pre[i - 1] + suf[i])
        if i >= 3:
            ans = max(ans, pre[i - 3] + suf[i])
    print(ans)