Given is an integer sequence A_1, ..., A_N of length N.

We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.

Find the maximum possible sum of the chosen elements.

Here \lfloor x \rfloor denotes the greatest integer not greater than x.

Constraints

* 2 \leq N \leq 2\times 10^5
* |A_i|\leq 10^9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 ... A_N


Output

Print the maximum possible sum of the chosen elements.

Examples

Input

6
1 2 3 4 5 6


Output

12


Input

5
-1000 -100 -10 0 10


Output

0


Input

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000


Output

5000000000


Input

27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49


Output

295
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
import random

# sys.stdin = open('input')

def inp():
    re = map(int, raw_input().split())
    if len(re) == 1:
        return re[0]
    return re

def inst():
    return raw_input().strip()

def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

def get(n, da):
    mx = 0
    for i in range(n):
        if i%2==1:
            mx += da[i]
    st = [0 for i in range(n)]
    dp = [0 for i in range(n)]
    st[0]=1
    dp[0]=da[0]
    for i in range(2,n):
        if i%2==0:
            st[i]=1
            dp[i]=dp[i-2]+da[i]
        else:
            st[i]=1
            dp[i] = dp[i-3]+da[i]
            if st[i-2]:
                dp[i] = max(dp[i], dp[i-2]+da[i])
    return max(mx, max(dp[n-1], dp[n-2]))

def my_main():
    n = inp()
    da = inp()
    if n%2==0:
        print get(n, da)
    else:
        nda = [da[i] for i in range(n) if i%2==0]
        mx = sum(nda) - min(nda)
        mx = max(mx, max(get(n-1, da[1:]), get(n-1, da[:-1])))
        st = [[0 for i in range(n)]for i in range(3)]
        dp = [[0 for i in range(n)]for i in range(3)]
        st[0][0]=1
        dp[0][0]=da[0]
        for i in range(2,n):
            if st[0][i-2]:
                st[0][i] = 1
                dp[0][i] = dp[0][i-2] + da[i]
            if i-3 >= 0 and st[0][i-3]:
                st[1][i] = 1
                dp[1][i] = dp[0][i-3] + da[i]
            if st[1][i-2]:
                st[1][i] = 1
                dp[1][i] = max(dp[1][i], dp[1][i-2] + da[i])
            if i-3>=0 and st[1][i-3]:
                st[2][i] = 1
                dp[2][i] = dp[1][i-3] + da[i]
            if st[2][i-2]:
                if st[2][i]:
                    dp[2][i] = max(dp[2][i], dp[2][i-2]+da[i])
                else:
                    st[2][i] = 1
                    dp[2][i] = dp[2][i-2]+da[i]
        print max(mx, dp[2][n-1])







my_main()
