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
import sys
sys.setrecursionlimit(10**7)

from functools import lru_cache

@lru_cache(None)
def dfs(p, remain):

    n = len(arr)

    if remain == 0 or p >= n:
        return 0

    if remain == 1:
        return max(arr[p:])
        
    len_remain = n - (p + 1)

    t = -float('inf')
    if (remain - 1) * 2 + 1 <= len_remain:
        t = dfs(p + 1, remain)

    t2 = arr[p] + dfs(p + 2, remain - 1)

    return max(t, t2)

    


n = int(input())

arr = list(map(int, input().split()))

ans = dfs(0, n // 2)

print (ans)

