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.

-----Sample Input-----
6
1 2 3 4 5 6

-----Sample Output-----
12

Choosing 2, 4, and 6 makes the sum 12, which is the maximum possible value.

Difficulty: interview

Starter code:

Solutions:
def main():
    import sys
    import numpy as np
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    a = list(map(int, input().split()))
    inf = 1e18
    k = n%2 + 1
    dp = np.full((n+1, k+2), -inf, dtype=int)
    dp[0,0] = 0
    for i in range(n):
        for j in range(k+1):
            dp[i+1, j+1] = max(dp[i+1,j+1],dp[i,j])
            now = dp[i,j]
            if (i+j)%2 == 0: now += a[i]
            dp[i+1,j] = max(dp[i+1,j],now)
    print(dp[n,k])

def __starting_point():
    main()
__starting_point()

import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
inf=float("inf")
DP=[[-inf]*4 for _ in range(n+1)]
DP[0][2]=0
for i,a in enumerate(A):
  if (i+1)%2==0:
    DP[i+1][0]=DP[i][3]+a
    if i>=1:
      DP[i+1][0]=max(DP[i+1][0],DP[i-1][2]+a)
    DP[i+1][2]=DP[i][0]
    DP[i+1][3]=max(DP[i][1],DP[i][3])
    if i>=1:
      DP[i+1][3]=max(DP[i+1][3],DP[i-1][2])
  else:
    DP[i+1][0]=DP[i][2]+a
    DP[i+1][1]=DP[i][3]+a
    DP[i+1][3]=max(DP[i][0],DP[i][2])
if n%2==0:
  print((max(DP[n][0],DP[n][2])))
else:
  print((max(DP[n][1],DP[n][3])))



#!/usr/bin/env python3
# coding: utf-8
import collections
def debug(arg):
    if __debug__:
        pass
    else:
        import sys
        print(arg, file=sys.stderr)

def main():
    pass
    N, *A = map(int, open(0).read().split())
    a = dict(enumerate(A, 1))
    dp = collections.defaultdict(lambda: -float("inf"))
    dp[0, 0] = 0 
    dp[1, 0] = 0 
    dp[1, 1] = a[1]
    for i in range(2, N + 1):
        jj = range(max(i // 2 - 1, 1), (i + 1) // 2 + 1)
        for j in jj:
            x = dp[i - 2, j - 1] + a[i]
            y = dp[i - 1, j]
            dp[i, j] = max(x, y)
    print(dp[N, N // 2])

def __starting_point():
    main()
__starting_point()

N = int(input())
A = list(map(int, input().split()))
inf = 10**18

x = N % 2 + 1
dp = [[-inf] * 4 for _ in range(N + 10)]
dp[0][0] = 0
for i, a in enumerate(A):
    for j in range(x + 1):
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])
        now = dp[i][j]
        if (i + j) % 2 == 0:
            now += a
        dp[i + 1][j] = max(dp[i + 1][j], now)

print(dp[N][x])

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

ret = 0

if n % 2 == 0:
    dp = [[0] * 2 for _ in range(n)]
    dp[0][0] = a[0]
    for i in range(1, n):
        dp[i][0] = dp[i-1][0] if i % 2 == 1 else dp[i-1][0] + a[i]
        dp[i][1] = dp[i - 1][1] if i % 2 == 0 \
            else max(dp[i-2][0], dp[i-2][1]) + a[i]
    ret = max(dp[-1])
else:
    dp = [[0] * 3 for _ in range(n)]
    dp[0][0] = a[0]
    for i in range(1, n):
        dp[i][0] = dp[i-1][0] if i % 2 == 1 else dp[i-1][0] + a[i]
        dp[i][1] = dp[i - 1][1] if i % 2 == 0 \
            else max(dp[i-2][0], dp[i-2][1]) + a[i]
        dp[i][2] = dp[i - 1][1] if i % 2 == 1 \
            else max(dp[i-3][0], dp[i-2][1], dp[i-2][2]) + a[i]
    ret = max(dp[-1][1], dp[-1][2], dp[-2][0])

print(ret)


#!/usr/bin/env python3
import sys

MOD = 1000000007

def solve(N: int, A: "List[int]"):
    from collections import defaultdict
    M = N // 2
    def get_range(idx):
        r = (N - idx) // 2 + 1        
        return list(range(max(0, M-r), idx//2+1+1))
    
    dp_a = defaultdict(lambda:-float('inf'))
    dp_s = defaultdict(lambda:-float('inf'))
    dp_s[(0, -1)] = 0 
    for i in range(N):
        for j in get_range(i):
            dp_s[(j, i)] = max(dp_s[(j, i)], dp_a[(j, i-1)], dp_s[(j, i-1)])
            dp_a[(j, i)] = max(dp_a[(j, i)], dp_s[(j, i)], dp_s[(j-1, i-1)]+A[i])
    print((max(max(v for (j, i), v in list(dp_a.items()) if j == M),
              max(v for (j, i), v in list(dp_s.items()) if j == M))))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

def __starting_point():
    main()

__starting_point()

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float("inf")
mod = 10 ** 9 + 7

N = INT()
A = LIST()

dp = [[0]*3 for _ in range(N+1)]
dp[0][0] = -INF
dp[1][0] = -INF
dp[1][2] = A[0]
for i in range(2, N+1):
	if i%2 == 1:
		dp[i][0] = max(dp[i-1][0], dp[i-2][0]+A[i-1])
		dp[i][1] = max(dp[i-1][1], dp[i-2][1]+A[i-1])
		dp[i][2] = dp[i-2][2]+A[i-1]
	else:
		dp[i][0] = max(dp[i-1][1], dp[i-2][0]+A[i-1])
		dp[i][1] = max(dp[i-1][2], dp[i-2][1]+A[i-1])

print((dp[N][1]))


#!/usr/bin/env python3
# coding: utf-8
import collections
import math
def debug(arg):
    if __debug__:
        pass
    else:
        import sys
        print(arg, file=sys.stderr)

def main():
    pass
    N, *A = map(int, open(0).read().split())
    a = dict(enumerate(A, 1))
    dp = collections.defaultdict(lambda: -float("inf"))
    dp[0, 0] = 0 
    dp[1, 0] = 0 
    dp[1, 1] = a[1]
    for i in range(2, N + 1):
        jj = range(max(math.floor(i // 2 - 1), 1), math.ceil((i + 1) // 2) + 1)
        for j in jj:
            x = dp[i - 2, j - 1] + a[i]
            y = dp[i - 1, j]
            dp[i, j] = max(x, y)
    print(dp[N, N // 2])

def __starting_point():
    main()
__starting_point()

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

inf = 10 ** 18

dp = [[-inf] * 3  for _ in range(n + 1)]
k = 1 + n % 2
dp[0][0] = 0
for i in range(n):
    for j in range(k + 1):
        if j < k:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
        now = dp[i][j]
        if (i + j) % 2 == 0:
            now += A[i]
        dp[i + 1][j] = max(dp[i + 1][j], now)
print((dp[n][k]))


N = int(input())
A = list(map(int,input().split()))
K = 2 if N%2 else 1
INF = float('inf')
dp = [[[-INF]*2 for _ in range(K+1)] for _ in range(N+1)]
dp[0][K][0] = 0 #dp[i][can_skip][must_skip]
for i,a in enumerate(A):
    for k in range(K,-1,-1):
        dp[i+1][k][0] = max(dp[i+1][k][0], dp[i][k][1])
        dp[i+1][k][1] = max(dp[i+1][k][1], dp[i][k][0] + a)
        if k:
            dp[i+1][k-1][0] = max(dp[i+1][k-1][0], dp[i][k][0])
print(max(max(row) for row in dp[-1][:2]))

N=int(input())
A=list(map(int, input().split()))

dp = [[0 for i in range(2)] for j in range(N+1)]

if N in [2, 3]: print(max(A))
else:
  dp[2][0] = A[1]
  dp[2][1] = A[0]
  dp[3][0] = A[2]
  dp[3][1] = max(A[1], A[0])
  
  for i in range(4, N+1):
    if i % 2 == 0:
      dp[i][0] = max(max(dp[i-2][0], dp[i-2][1])+A[i-1], dp[i-1][1]+A[i-1])
      dp[i][1] = dp[i-2][1]+A[i-2]
    else:
      dp[i][0] = max(dp[i-2][0], dp[i-2][1])+A[i-1]
      dp[i][1] = max(dp[i-1][0], dp[i-1][1])

  print(max(dp[-1][0], dp[-1][1]))

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

from collections import*
n,*a=map(int,open(0).read().split())
dp=[defaultdict(lambda:-10**18)for _ in range(n)]
for i in range(n):dp[i][0]=0
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i][j]=max(dp[i-2][j],dp[i-2][j-1]+a,dp[i-1][j])
print(dp[-1][n//2])

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

dp = [[0]*2 for _ in range(n+1)]
dp[1] = [0,a[0]]
dp[2] = [0,max(a[0],a[1])]
for i in range(3,n+1):
    if i%2 == 0:
        dp[i][0] = max(dp[i-1][0],dp[i-2][0]+a[i-1])
        dp[i][1] = max(dp[i-1][1],dp[i-2][1]+a[i-1])
    else:
        dp[i][0] = max(dp[i-1][1],dp[i-2][0]+a[i-1])
        dp[i][1] = dp[i-2][1]+a[i-1]
        
if n%2 == 0:
    print(dp[n][1])
else:
    print(dp[n][0])

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = LI()

    if n < 4:
        return max(a)

    dp = [[-inf] * 3 for _ in range(n)]
    for i in range(3):
        dp[i][i] = a[i]

    for i in range(n):
        c = a[i]
        di = dp[i]
        if i > 1:
            d2 = dp[i-2]
            for j in range(3):
                if di[j] < d2[j] + c:
                    di[j] = d2[j] + c
        if i > 2:
            d3 = dp[i-3]
            for j in range(2):
                if di[j+1] < d3[j] + c:
                    di[j+1] = d3[j] + c
        if i > 3:
            d4 = dp[i-4]
            for j in range(1):
                if di[j+2] < d4[j] + c:
                    di[j+2] = d4[j] + c

    if n % 2 == 0:
        return max(dp[-1][1], dp[-2][0])

    r = -inf
    for i in range(3):
        r = max(r, dp[-1-i][2-i])

    return r

print(main())





n = int(input())
a = list(map(int, input().split()))
if n % 2 == 0 and n >= 4:
  dp = [[0, 0] for i in range(n)]
  dp[0][0] = a[0]
  dp[1][1] = a[1]
  dp[2][0] = a[0] + a[2]
  for i in range(3, n):
    dp[i][0] = dp[i - 2][0] + a[i]
    dp[i][1] = max(dp[i - 3][0], dp[i - 2][1]) + a[i]
  print(max(dp[n - 2][0], dp[n - 1][1]))
elif n % 2 != 0 and n >= 5:
  dp = [[0, 0, 0] for i in range(n)]
  dp[0][0] = a[0]
  dp[1][1] = a[1]
  dp[2][0] = a[0] + a[2]
  dp[2][2] = a[2]
  dp[3][1] = a[1] + a[3]
  dp[3][2] = a[0] + a[3]
  for i in range(3, n):
    dp[i][0] = dp[i - 2][0] + a[i]
    dp[i][1] = max(dp[i - 3][0], dp[i - 2][1]) + a[i]
    dp[i][2] = max(dp[i - 4][0], dp[i - 3][1], dp[i - 2][2]) + a[i]
  print(max(dp[n - 3][0], dp[n - 2][1], dp[n - 1][2]))
elif n == 2:
  print(max(a[0], a[1]))
else:
  print(max(a[0], a[1], a[2]))

import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def odd(A):
    oddi=np.array(A[::2],dtype=np.int64)
    eveni=np.array(A[1::2],dtype=np.int64)
    left=np.cumsum(oddi[:-1]-eveni)
    left=np.insert(left,0,0)
    left=np.append(left,0)
    right=np.cumsum(oddi[:0:-1]-eveni[::-1])[::-1]
    right=np.insert(right,0,0)
    right=np.append(right,0)
    tmp=np.max(np.maximum.accumulate(left)+right)
    return tmp+np.sum(eveni)

def even(A):
    left=np.array([0]+A[::2],dtype=np.int64)
    right=np.array(A[1::2]+[0],dtype=np.int64)[::-1]
    return np.max(left.cumsum()+right.cumsum()[::-1])

def main():
    n=int(input())
    A=list(map(int, input().split()))
    if n%2==1:
        print(odd(A))
    else:
        print(even(A))


def __starting_point():
    main()
__starting_point()

# 写経AC
from collections import defaultdict

N = int(input())
A = [int(i) for i in input().split()]

# dp[(i, x, flag)]:= i番目まででx個選んでいる時の最大値
# flag: i番目をとるフラグ
dp = defaultdict(lambda: -float("inf"))

# 初期条件
dp[(0, 0, 0)] = 0

# 貰うDP
for i, a in enumerate(A, 1):
    # i番目までで選ぶ個数
    for x in range((i // 2) - 1, (i + 1) // 2 + 1):
        dp[(i, x, 0)] = max(dp[(i - 1, x, 0)], dp[(i - 1, x, 1)])
        dp[(i, x, 1)] = dp[(i - 1, x - 1, 0)] + a

print(max(dp[(N, N // 2, 0)], dp[(N, N // 2, 1)]))

from itertools import accumulate
n = int(input())
A = list(map(int, input().split()))
L = [0]
R = []
min_L = float("inf")
for i, a in enumerate(A):
  b = A[-(i+1)]
  if i%2 == 0:
    L.append(a)
  else:
    R.append(a)
R.append(0)
L = list(accumulate(L))
R = list(accumulate(R[::-1]))[::-1]
ans = -float("inf")
if n%2:
  def f(A):
    temp = 0
    left = 0
    right = 0
    for i in range(2, n, 2):
      temp += A[i]
    res = max(ans, temp)
    for i in range(1, n//2):
      temp -= A[i*2]
      left, right = left+A[2*(i-1)], max(left, right)+A[2*(i-1)+1]
      res = max(res, temp+max(left, right))
    return res
  ans = max(f(A), f(A[::-1]))
  temp = 0
  for i in range(1, n, 2):
    temp += A[i]
  ans = max(ans, temp)
else:
  for l, r in zip(L, R):
    ans = max(ans, l+r)
print(ans)

INF = 10**18

def solve(n, a):
    # 現在の位置 x 選んだ個数 x 直前を選んだかどうか
    dp = [{j: [-INF, -INF] for j in range(i//2-1, (i+1)//2 + 1)} for i in range(n+1)]
    dp[0][0][False] = 0
    for i in range(n):
        for j in dp[i].keys():
            if (j+1) in dp[i+1]:
                dp[i+1][j+1][True] = max(dp[i+1][j+1][True], dp[i][j][False] + a[i])
            if j in dp[i+1]:
                dp[i+1][j][False] = max(dp[i+1][j][False], dp[i][j][False])
                dp[i+1][j][False] = max(dp[i+1][j][False], dp[i][j][True])
    return max(dp[n][n//2])

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

import numpy as np
n = int(input())
a = list(map(int,input().split()))

dp = np.zeros((n+1,2), int)
dp[1],dp[2] = [0,a[0]], [0,max(a[0], a[1])]
for i in range(3,n+1):
  if(i%2 == 0):
    dp[i][0] = max(dp[i-1][0],dp[i-2][0]+a[i-1],dp[i-2][1])
    dp[i][1] = max(dp[i-1][1],dp[i-2][1]+a[i-1])
  else:
    dp[i][0] = max(dp[i-1][1],dp[i-2][1],dp[i-2][0]+a[i-1])
    dp[i][1] = dp[i-2][1]+a[i-1]
print(dp[n][(n+1)%2])

N = int(input())
A = list(map(int, input().split()))

DP_odd = [0, 0, A[0]]
DP_even = [0, max(A[0], A[1])]

if N >= 3:
    DP_odd = [DP_even[0], max(DP_odd[1] + A[2], DP_even[1]), DP_odd[2] + A[2]]

for i in range(3, N):
    if (i + 1) % 2 == 1:    
        DP_odd = [max(DP_odd[0] + A[i], DP_even[0]), max(DP_odd[1] + A[i], DP_even[1]), DP_odd[2] + A[i]]
    else:
        DP_even = [max(DP_even[0] + A[i], DP_odd[1]), max(DP_even[1] + A[i], DP_odd[2])]

if N % 2 == 1:
    ans = DP_odd[1]
else:
    ans = DP_even[1]

print(ans)

N = int(input())
A = list(map(int, input().split())) + [0]

dp0, dp1, dp2 = [0] * (N + 1), [0] * (N + 1), [0] * (N + 1)
dp0[0] = A[0]
dp1[1] = A[1]
dp2[2] = A[2]

for i in range(N - 3):
    dp0[i + 2] = 0 if i % 2 else dp0[i] + A[i + 2]
    dp1[i + 3] = max(dp0[i], dp1[i + 1]) + A[i + 3]
    dp2[i + 4] = max(dp0[i], dp1[i + 1], dp2[i + 2]) + A[i + 4]

if N % 2:
    print((max(dp0[N - 3], dp1[N - 2], dp2[N - 1])))
else:
    print((max(dp0[N - 2], dp1[N - 1])))


N = int(input())
A = [int(x) for x in input().split()]

x, y, z = A[0], A[1], 0
for i in range(2, N):
    if i % 2 == 0:
        z = z + A[i]
        y = max(y, x)
        x = x + A[i]
    else:
        z = max(y, z)
        y = y + A[i]
        x = x

if N % 2 == 0:
    print((max(x, y)))
else:
    print((max(y, z)))


N=int(input())
A=list(map(int, input().split()))
if N==2:
  print(max(A))
  return 
  
dp=[[0,0,0] for i in range(N)]
dp[0][0]=A[0]
dp[1][1]=A[1]
dp[2][2]=A[2]
for i in range(N):
  if i>1:
    dp[i][0]=dp[i-2][0]+A[i]
  if i>2:
    dp[i][1]=max(dp[i-3][0],dp[i-2][1])+A[i]
  if i>3 :
    dp[i][2]=max(dp[i-4][0],dp[i-3][1],dp[i-2][2])+A[i]
if N%2==1:
  ans=max(dp[-1][2],dp[-2][1],dp[-3][0])
else:
  ans=max(dp[-1][1],dp[-2][0])
print(ans)

N = int(input())
A = list(map(int, input().split()))
INF = 10**18

dp0 = 0
dp1 = -INF
dp2 = -INF

for i, a in enumerate(A):
    if i % 2 == 0:
        dp1 = max(dp1, dp0)
        dp0 += a
        dp2 += a
    else:
        dp2 = max(dp2, dp1)
        dp1 += a

if N % 2 == 1:
    print((max(dp1, dp2)))
else:
    print((max(dp0, dp1)))


n=int(input())
arr=list(map(int,input().split()))
acum1=[0]
acum2=[0]
for i in range(n):
  if i%2==0:
    acum1.append(acum1[-1]+arr[i])
    acum2.append(acum2[-1]+0)
  else:
    acum1.append(acum1[-1]+0)
    acum2.append(acum2[-1]+arr[i])
if n%2==0:
  ans=max(acum1[n-1]-acum1[0],acum2[n]-acum2[1])
  for i in range(1,n+1,2):
    if i+3>n:
      continue
    tmp=(acum1[i]-acum1[0])+(acum2[n]-acum2[i+2])
    ans=max(ans,tmp)
else:
  ans=max(acum1[n-2]-acum1[0],acum2[n-1]-acum2[1],acum1[n]-acum1[2])
  for i in range(1,n+1,2):
    if i+3>n-1:
      continue
    tmp=(acum1[i]-acum1[0])+(acum2[n-1]-acum2[i+2])
    ans=max(ans,tmp)
  for i in range(2,n+1,2):
    if i+3>n:
      continue
    tmp=(acum2[i]-acum2[1])+(acum1[n]-acum1[i+2])
    ans=max(ans,tmp)
  for i in range(1,n+1,2):
    if i+4>n:
      continue
    tmp=(acum1[i]-acum1[0])+(acum1[n]-acum1[i+3])
    ans=max(ans,tmp)
  acummax=[-10**18]
  for i in range(1,n+1):
    if i+2>n:
      acummax.append(-10**18)
    else:
      if i%2==0:
        acummax.append(acum2[i]+acum1[n]-acum1[i+2])
      else:
        acummax.append(-10**18)
  for i in range(n-1,-1,-1):
    acummax[i]=max(acummax[i],acummax[i+1])
  for i in range(1,n+1,2):
    if i+6>n:
      continue
    tmp=(acum1[i]-acum1[0]-acum2[i+2])+acummax[i+3]
    ans=max(ans,tmp)
print(ans)

import sys

N = int(input()); A = list(map(int,input().split()))

if N == 2:
    print(max(A))
    return

dp = [0,max(A[:3]),A[0]+A[2]]
tmp1 = dp[:]
tmp2 = [0,max(A[:2]),0]
flag1 = False
flag2 = True if A[0] < A[2] and A[1] < A[2] else False
flag3 = False

for i in range(3,N):
    b = A[i]
    if i%2 == 0:
        dp[0] = max(tmp2[0],tmp1[0]+b)
        flag1 = True if tmp2[0] < tmp1[0]+b else False
        if flag3:
            dp[1] = max(tmp2[1],tmp1[1]+b)
            flag2 = True if tmp2[1] < tmp1[1]+b else False 
        else:
            dp[1] = max(tmp2[1],tmp2[0]+b,tmp1[1]+b)
            flag2 = True if tmp2[1] < tmp2[0]+b or tmp2[1] < tmp1[1]+b else False 
        dp[2] += A[i]
        tmp1 = dp[:]
    else:
        if flag1:
            dp[0] = max(tmp1[1],tmp2[0]+b)
            flag3 = True if tmp1[1] < tmp2[0]+b else False
        else:
            dp[0] = max(tmp1[1],tmp1[0]+b,tmp2[0]+b)
            flag3 = True if tmp1[1] < tmp1[0]+b or tmp1[1] < tmp2[0]+b else False
        if flag2:
            dp[1] = max(tmp1[2],tmp2[1]+b)
        else:
            dp[1] = max(tmp1[2],tmp1[1]+b,tmp2[1]+b)
        tmp2 = dp[:]
        
print (dp[1])

def f_select_half():
    # 参考: https://at274.hatenablog.com/entry/2020/04/14/002124
    from collections import defaultdict
    N = int(input())
    A = [int(i) for i in input().split()]

    # dp[(i, j, flag)]: A の i 番目の要素まで見たとき、j 個の要素を選んでいるときの和の最大値
    # flag == 1 のときは、i 番目の要素を採用したものとする
    # 初めて指した遷移前が影響してほしくないので、この値で初期化
    dp = defaultdict(lambda: -float('inf'))
    dp[(0, 0, 0)] = 0

    for k, a in enumerate(A, 1):
        j = k // 2
        for x in range(j - 1, j + 2):
            dp[(k, x, 0)] = max(dp[(k - 1, x, 0)], dp[k - 1, x, 1])
            # k-1 番目の要素を選んでいないときだけ、k 番目の要素を選べる
            dp[(k, x, 1)] = dp[(k - 1, x - 1, 0)] + a
    return max(dp[(N, N // 2, f)] for f in (0, 1))

print(f_select_half())

from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
dp=[defaultdict(lambda:-float('inf'))for _ in range(n)]
for i in range(n):dp[i][0]=0
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i][j]=max(dp[i-2][j],dp[i-2][j-1]+a,dp[i-1][j])
print((dp[-1][n//2]))


# 写経AC
from collections import defaultdict

N = int(input())
A = [int(i) for i in input().split()]

# dp[(i, x, flag)]:= i番目まででx個選んでいる時の最大値
# flag: i番目をとるフラグ
dp = defaultdict(lambda: -float("inf"))

# 初期条件
dp[(0, 0, 0)] = 0

for i, a in enumerate(A, 1):
    for x in range((i // 2) - 1, (i + 1) // 2 + 1):
        dp[(i, x, 0)] = max(dp[(i - 1, x, 0)], dp[(i - 1, x, 1)])
        dp[(i, x, 1)] = dp[(i - 1, x - 1, 0)] + a

print(max(dp[(N, N // 2, 0)], dp[(N, N // 2, 1)]))

import sys
sys.setrecursionlimit(2000000000)
N = int(input())
import math
l = [int(x) for x in input().split()]
tobi = [0]*(math.ceil(N/2))
tobi[0] = l[0]
for i in range(1,math.ceil(N/2)):
    tobi[i] = tobi[i-1] + l[i*2]
from functools import lru_cache
@lru_cache(maxsize=1000000000)
def motomeru(x,y):
    if y == 0 or x == 0 or x == 1:
        return 0
    elif x % 2 == 0:
        return max(motomeru(x-2,y-1)+l[x-1],tobi[math.floor((x-1)/2)])
    else:
        return max(motomeru(x-2,y-1)+l[x-1],motomeru(x-1,y))
print(motomeru(N,N//2))

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

# oを選択 xを非選択とする　左から見て
# oxoxoxoxoxo に x を1つか2つ挿入することを考える
# 状態を4つ設定 (最後がxかoか)(挿入ずみのxの数)の形式でやる
#a=[1,2,3,4,5,6,7]
#n=len(a)
x0,x1,x2,o0,o1,o2=a[0],-10**18,0,-10**18,a[1],-10**18
for i in a[2:]:
    x0,x1,x2,o0,o1,o2=o0,max(o1,x0),max(o2,x1),x0+i,x1+i,x2+i
if n%2==0:
    print(max(x0,x1,o1))
else:
    print(max(x1,x2,o2))


def resolve():
    INF = float("-inf")
    N = int(input())
    A = list(map(int, input().split()))

    # 取る 取らない 取る 取らない ... を貪欲にやっていくと 1 + n % 2 個余って、
    # 1 + n % 2 回飛ばせることがわかる
    skip = 1 + N % 2;

    # dp[i][j] := a[0, i) を j 要素無視して1つ飛びに取ったときの最大値
    dp = [[INF] * (skip + 1) for _ in range(N + 2)]
    dp[0][0] = 0
    for i in range(N + 1):
        for j in range(skip + 1):
            if j < skip:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
            if i < N:
                dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + A[i])
    # 1個選んだら1個選ばないのもセット
    # なので floor(n / 2) * 2 + skip == n + 1 に答えが入る
    print((dp[N + 1][skip]))


def __starting_point():
    resolve()

__starting_point()

#!/usr/bin/env python3
import sys
from itertools import accumulate
sys.setrecursionlimit(10**8)
INF = float("inf")

import math


def array(*args, initial=0):
    pre = "["*len(args)
    post = ""
    for a in args[::-1]:
        post += " for _ in range("+str(a)+")]"
    S = pre + str(initial) + post
    return eval(S)


def solve(N: int, A: "List[int]"):

    if N % 2 == 0:
        K = 2
    else:
        K = 3

    DP = array(N, K, initial=-10**9)
    DP[0][0] = A[0]
    DP[1][1] = A[1]
    if K == 3:
        DP[2][2] = A[2]
    for i in range(1, N):
        for k in range(K):
            if i == k and i < K:
                continue
            DP[i][k] = DP[i-2][k]
            if k-1 >= 0:
                DP[i][k] = max(DP[i][k], DP[i-3][k-1])
            if k-2 >= 0:
                DP[i][k] = max(DP[i][k], DP[i-4][k-2])
            DP[i][k] += A[i]
    if N % 2 == 0:
        print((max(DP[-1][1], DP[-2][0])))
    else:
        print((max(DP[-1][2], DP[-2][1], DP[-3][0])))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


def __starting_point():
    main()

__starting_point()

n=int(input())
a=list(map(int,input().split()))
dp=[0]#dp[i]=左からi番目までで(i//2)個選んだときの最大値
sum_odd=a[0]

dp.append(0)
for i in range(2,n+1):
  if i%2==1:
    sum_odd+=a[i-1]
    dp.append(max(dp[i-1],dp[i-2]+a[i-1]))
  else:
    dp.append(max(sum_odd,a[i-1]+dp[i-2]))
print((dp[n]))


from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

# dp[(i, x, flg)] := i番目までみてx個選んでいる時の最大値。flgは最後の１つをとったかどうか。
dp = defaultdict(lambda: -float('inf'))
dp[(0, 0, 0)] = 0

for i, a in enumerate(A, start=1):
    for x in range((i - 1) // 2, (i + 1) // 2 + 1):
        dp[(i, x, 0)] = max(dp[(i - 1, x, 0)], dp[(i - 1, x, 1)])
        dp[(i, x, 1)] = dp[(i - 1, x - 1, 0)] + a

print((max(dp[(N, N // 2, 0)], dp[(N, N // 2, 1)])))


from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

dp = defaultdict(lambda: -float('inf'))
dp[(0, 0, 0)] = 0

for i, a in enumerate(A, start=1):
    j = i // 2
    for x in range(j - 1, j + 2):
        dp[(i, x, 0)] = max(dp[(i - 1, x, 0)], dp[(i - 1, x, 1)])
        dp[(i, x, 1)] = dp[(i - 1, x - 1, 0)] + a

print(max(dp[(N, N // 2, 0)], dp[(N, N // 2, 1)]))

n = int(input())
a = list(map(int,input().split()))
 
dp = [[0]*2 for _ in range(n+1)]
dp[1] = [0,a[0]]
dp[2] = [0,max(a[0],a[1])]
for i in range(3,n+1):
    if i%2 == 0:
        dp[i][0] = max(dp[i-1][0],dp[i-2][0]+a[i-1])
        dp[i][1] = max(dp[i-1][1],dp[i-2][1]+a[i-1])
    else:
        dp[i][0] = max(dp[i-1][1],dp[i-2][0]+a[i-1])
        dp[i][1] = dp[i-2][1]+a[i-1]
        
if n%2 == 0:
    print(dp[n][1])
else:
    print(dp[n][0])

def find_max(a):
    n = len(a)

    if n <= 3:
        return max(a)

    dp = [[-(1 << 64)] * (2 + n % 2) for _ in range(n)]

    for i in range(2 + n % 2):
        dp[i][i] = a[i]
        dp[i + 1][i] = a[i]

    for i in range(2, n):
        for j in range(2 + n % 2):
            for extra_space in range(j + 1):
                curr_sum = dp[i - (2 + extra_space)][j - extra_space] + a[i]
                if curr_sum > dp[i][j]:
                    dp[i][j] = curr_sum

    return dp[-1][1 + n % 2]


def main():
    _ = int(input())
    a = list(map(int, input().split()))

    print((find_max(a)))


main()


n=int(input())
if n%2:
  a=list(map(int,input().split()))
  s=[[a[0],0,0],[0,a[1],0],[a[0]+a[2],0,a[2]]]+[[0,0,0]for i in range(3,n)]
  for i in range(3,n):
    if i%2:
      s[i][1]=max(s[i-2][1],s[i-3][0])+a[i]
    else:
      s[i][0]=s[i-2][0]+a[i]
      s[i][2]=max([s[i-2][2],s[i-3][1],s[i-4][0]])+a[i]
  print(max([s[-1][2],s[-2][1],s[-3][0]]))
else:
  a=list(map(int,input().split()))
  s=[a[0],a[1]]+[0 for i in range(2,n)]
  for i in range(2,n):
    if i%2:
      s[i]=max([s[i-2],s[i-3]])+a[i]
    else:
      s[i]=s[i-2]+a[i]
  print(max(s[-2:]))

N_all=int(input())
A=list(map(int,input().split()))
f_inf=-float("inf")
odds_or_even=N_all%2+2
dp=[[f_inf for x in range(N_all+1)] for x in range(odds_or_even)]
dp[0][0]=0

for i in range(N_all):
  dp[0][i+1]=dp[0][i]+A[i]*((i+1)%2)
for j in range(1,odds_or_even):
  for i in range(N_all):
    dp[j][i+1]=max(dp[j][i]+A[i]*((i+j+1)%2),dp[j-1][i])
        
print(dp[odds_or_even-1][N_all])

from collections import defaultdict

INF = float("inf")


N, *A = map(int, open(0).read().split())

I = defaultdict(lambda: -INF)
O = defaultdict(lambda: -INF)
O[(0, 0)] = 0

for i, a in enumerate(A, 1):
    j = (i - 1) // 2
    for n in [j, j + 1]:
        I[(i, n)] = a + O[(i - 1, n - 1)]
        O[(i, n)] = max(O[(i - 1, n)], I[(i - 1, n)])

print(max(I[(N, N // 2)], O[(N, N // 2)]))

def main():
    INF = 10 ** 18
    N = int(input())
    A = list(map(int, input().split(' ')))
    K = 1 + N % 2  # 余分な×を入れられる個数
    # dp[i][j]: i個目までの要素で余分な×をj個使った際の最大値
    dp = [[- INF for _ in range(K + 1)] for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(K + 1):
            if j < K:
                # 余分な×を使う場合
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
            # 余分な×を使わない場合
            now = dp[i][j]
            if (i + j) % 2 == 0:
                # 基本はi % 2 == 0の時にA[i]を足していく
                # ただ、余分な×がj個入っていると、その分ずれる
                now += A[i]
            dp[i + 1][j] = max(dp[i + 1][j], now)
    print((dp[N][K]))


def __starting_point():
    main()

__starting_point()

N = int(input())
A = [int(a) for a in input().split()]
if N % 2 == 0:
    x, y, px, py = 0, 0, 0, -1<<100
    for a in A:
        x, y, px, py = px+a, max(x, py+a), x, y
    print(max(x, y))
else:
    x, y, z, px, py, pz = 0, 0, 0, 0, -1<<100, -1<<100
    for a in A:
        x, y, z, px, py, pz = px+a, max(x, py+a), max(y, pz+a), x, y, z
    print(max(y, z))

n = int(input())
a = list(map(int,input().split()))
m0 = 0
m1 = 0
m2 = 0

if n%2 == 0:
    for i,ai in enumerate(a):
        if i%2 == 0:
            m0 += ai
        else:
            m1 = max(m0,m1+ai)
    print((max(m0,m1)))
else:
    for i,ai in enumerate(a):
        if i%2 == 0:
            if i > 0:
                m2 = max(m2+ai,m1,m0)
            if i < n-1:
                m0 += ai
        else:
            m1 = max(m0,m1+ai)
    print((max(m0,m1,m2)))


import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def odd(A):
    oddi=np.array(A[::2],dtype=np.int64)
    eveni=np.array(A[1::2],dtype=np.int64)
    left=np.cumsum(oddi[:-1]-eveni)
    left=np.insert(left,0,0)
    right=np.cumsum(oddi[:0:-1]-eveni[::-1])[::-1]
    right=np.append(right,0)
    tmp=np.max(np.maximum.accumulate(left)+right)
    return tmp+np.sum(eveni)

def even(A):
    left=np.array([0]+A[::2],dtype=np.int64)
    right=np.array(A[1::2]+[0],dtype=np.int64)[::-1]
    return np.max(left.cumsum()+right.cumsum()[::-1])

def main():
    n=int(input())
    A=list(map(int, input().split()))
    if n%2==1:
        print(odd(A))
    else:
        print(even(A))


def __starting_point():
    main()
__starting_point()

from collections import defaultdict
N,*A = map(int, open(0).read().split())
dic1 = defaultdict(lambda :-10**20)
dic2 = defaultdict(lambda :-10**20)
for i in range(-1,N):
  dic1[(i,0)] = 0
  dic2[(i,0)] = 0
for i in range(N):
  for j in range(max(1,N//2-(N-i+1)//2), i//2+2):
    dic1[(i,j)] = max(dic1[(i,j)],dic2[(i-1,j-1)]+A[i])
  for j in range(N//2-(N-i)//2,(i-1)//2+2):
    dic2[(i,j)] = max(dic2[(i-1,j)],dic1[(i-1,j)])
print(max(dic1[(N-1,N//2)],dic2[(N-1,N//2)]))

from collections import defaultdict

INF = float("inf")

N, *A = map(int, open(0).read().split())

dp = defaultdict(lambda: -INF)
dp[(0, 0, False)] = 0

for i, a in enumerate(A, 1):
    p = i // 2
    for j in [p - 1, p, p + 1]:
        dp[(i, j, True)] = a + dp[(i - 1, j - 1, False)]
        dp[(i, j, False)] = max(dp[(i - 1, j, False)], dp[(i - 1, j, True)])

print(max(dp[(N, N // 2, True)], dp[(N, N // 2, False)]))

#!/usr/bin/env python3
# coding: utf-8
import collections
import math
def debug(arg):
    if __debug__:
        pass
    else:
        import sys
        print(arg, file=sys.stderr)

N, *A = map(int, open(0).read().split())
a = dict(enumerate(A, 1))
# dp = collections.defaultdict(int)
dp = collections.defaultdict(lambda: -float("inf"))
dp[0, 0] = 0 
dp[1, 0] = 0 
dp[1, 1] = a[1]
for i in range(2, N + 1):
    jj = range(max(math.floor(i // 2 - 1), 1), math.ceil((i + 1) // 2) + 1)
    debug(jj)
    for j in jj:
        x = dp[i - 2, j - 1] + a[i]
        y = dp[i - 1, j]

        dp[i, j] = max(x, y)
        debug([i - 2, j - 1])
        debug([i - 1, j])
        debug([i, j])
        debug(dp[i, j])
print(dp[N, N // 2])

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

# dp[(i, x, flg)] := i番目までみてx個選んでいる時の最大値。flgは最後の１つをとったかどうか。
dp = defaultdict(lambda: -float('inf'))
dp[(0, 0, 0)] = 0

for i, a in enumerate(A, start=1):
    j = i // 2
    for x in range(j - 1, j + 2):
        dp[(i, x, 0)] = max(dp[(i - 1, x, 0)], dp[(i - 1, x, 1)])
        dp[(i, x, 1)] = dp[(i - 1, x - 1, 0)] + a

print((max(dp[(N, N // 2, 0)], dp[(N, N // 2, 1)])))


def solve():
    INF = float('inf')

    def max2(x, y): return x if x >= y else y

    N = int(input())
    As = list(map(int, input().split()))

    dp = [[[-INF]*(2) for j in range(3)] for i in range(N+1)]
    dp[0][2][0] = dp[0][2][1] = 0
    for i, A in enumerate(As):
        if i&1:
            for k in range(2):
                for j in range(3):
                    dp[i+1][j][0] = max2(dp[i+1][j][0], dp[i][j][k])
            for j in range(2):
                dp[i+1][j+1][1] = max2(dp[i+1][j+1][1], dp[i][j][0] + A)
        else:
            for j in range(3):
                dp[i+1][j][1] = max2(dp[i+1][j][1], dp[i][j][0] + A)
            for k in range(2):
                for j in range(1, 3):
                    dp[i+1][j-1][0] = max2(dp[i+1][j-1][0], dp[i][j][k])

    if N&1:
        print((max(dp[-1][1])))
    else:
        print((max(dp[-1][2])))


solve()


n=int(input())
a = list(map(int,input().split()))
x0,x1,x2,o0,o1,o2=a[0],-10**18,0,-10**18,a[1],-10**18
for i in a[2:]:
  x0,x1,x2,o0,o1,o2=o0,max(o1,x0),max(o2,x1),x0+i,x1+i,x2+i
print(max(x0,x1,o1)if n%2==0 else max(x1,x2,o2))

from math import inf


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

dp = [[-inf] * 3  for _ in range(n + 1)]
k = 1 + n % 2
dp[0][0] = 0
for i in range(n):
    for j in range(k + 1):
        if j < k:
            dp[i + 1][j + 1] = dp[i][j]
        now = dp[i][j]
        if (i + j) % 2 == 0:
            now += A[i]
        dp[i + 1][j] = max(dp[i + 1][j], now)
print((dp[n][k]))


from collections import defaultdict

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

dp = defaultdict(lambda: -10**18)
dp[(0,0,False)] = 0

for i in range(n):
    for j in range(i//2-1,i//2+2):
        dp[(i+1,j,False)] = max(
            dp[(i,j,False)],
            dp[(i,j,True)]
        )
        dp[(i+1,j,True)] = dp[(i,j-1,False)] + al[i]

print((max(
    dp[(n,n//2,False)],
    dp[(n,n//2,True)]
)))


n = int(input())
A = list(map(int,input().split()))
dp = [[[0,0,0] for i in range(2)] for i in range(n+1)]
for i in range(1,n+1):
    if i%2 == 1:
        if i > 1:
            dp[i][0][1] = dp[i-1][1][0]+A[i-1]
            dp[i][0][2] = dp[i-1][1][1]+A[i-1]
            dp[i][1][0] = max(dp[i-1][0][0],dp[i-1][1][0])
            dp[i][1][1] = max(dp[i-1][0][1],dp[i-1][1][1])
        else:
            dp[i][0][2] = A[0]
    else:
        dp[i][0][0] = dp[i-1][1][0]+A[i-1]
        dp[i][0][1] = dp[i-1][1][1]+A[i-1]
        dp[i][1][0] = max(dp[i-1][0][1],dp[i-1][1][1])
        dp[i][1][1] = dp[i-1][0][2]
if n%2 == 0:
    print(max(dp[n][0][1],dp[n][1][1]))
else:
    print(max(dp[n][0][1],dp[n][1][1]))

n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
dp = [[0] * (n + 1) for _ in range(3)]
for i in range(n % 2 + 2):
    for j in range(1 + i, n + i, 2):
        if i == 0:
            if j == 1:
                dp[i][j] = a[j]
            else:
                dp[i][j] = dp[i][j - 2] + a[j]
        else:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 2] + a[j])
ans = dp[n % 2 + 1][n]
print(ans)

import numpy as np
n = int(input())
a = list(map(int,input().split()))
dp = np.full((2, n//2 + 1), -10**18, dtype=np.int64)
"""
dp[i][j] := iは偶奇, jは何個決めるか
"""
dp[0][0] = 0
dp[1][0] = 0
for i in range(n):
	k = i % 2
	for j in [2, 1, 0]:
		if i//2+j <= n//2:
			if i//2-1+j >= 0:
				dp[k][i//2+j] = np.maximum(dp[1-k][i//2+j], dp[k][i//2-1+j]+a[i])

print(max(dp[0][n//2], dp[1][n//2]))

N, *A = list(map(int, open(0).read().split()))

v1 = 0
v2 = 0
v3 = 0
m = N // 2 *2 
if N % 2 == 0:
  for i in range(0, m, 2):
    v1 += A[i]
    v2 += A[i+1]
    v2 = max(v1,v2)
  print(v2)  
#
else:
  for i in range(0, m, 2):
    v1 += A[i]
    v2 += A[i+1]
    v3 += A[i+2]
    v2 = max(v1,v2)
    v3 = max(v2,v3)
  print(v3)
#
  


N = int(input())
A = list(map(int, input().split()))
k = 1+N%2 # 余分なxを入れる個数
INF = 10**18
# dp: i番目まで見たときに、j個の余分なxを入れた時の、和の最大値
dp = [[-INF for _ in range(4)] for _ in range(202020)]
dp[0][0] = 0
for i in range(N):
    for j in range(k+1):
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]) # xを一つ挿入する=>今見てる数字をスキップする
        now = dp[i][j]
        if (i+j)%2==0:
            now += A[i]
        dp[i+1][j] = max(dp[i+1][j], now)
print(dp[N][k])

#!/usr/bin/env python3
import sys

MOD = 1000000007

def solve(N: int, A: "List[int]"):
    from collections import defaultdict
    M = N // 2
    def get_range(idx):
        r = (N - idx) // 2 + 1        
        return list(range(max(0, M-r), idx//2+1+1))
    
    dp_a = defaultdict(lambda:-float('inf'))
    dp_s = defaultdict(lambda:-float('inf'))
    dp_s[(0, -1)] = 0 
    for i in range(N):
        for j in get_range(i):
            dp_s[(j, i)] = max(dp_s[(j, i)], dp_a[(j, i-1)], dp_s[(j, i-1)])
            dp_a[(j, i)] = max(dp_a[(j, i)], dp_s[(j, i)], dp_s[(j-1, i-1)]+A[i])
    print((max(max(v for (j, i), v in list(dp_a.items()) if j == M),
              max(v for (j, i), v in list(dp_s.items()) if j == M))))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

def __starting_point():
    main()

__starting_point()

from collections import defaultdict

n=int(input())
a=list(map(int,input().split()))
#n=2*pow(10,5)
#a=range(1,pow(10,5)+1)
# dp[i][j]:i番目の数字の中からj個数字を取った時の最大。(i//2)-1<=j<=(i+1)//2
# 求めるのはdp[n][n//2]
dp=defaultdict(lambda:-pow(10,18))
dp[(1,1)]=a[0]
for i in range(2,n+1): #i番目の数字はa[i-1]
      for j in range(i//2-1,(i+1)//2+1):
            if j==1:
                  dp[(i,j)]=max(dp[(i-1,1)],a[i-1])
            elif j==0:
                  dp[(i,j)]=0
            else:
                  dp[(i,j)]=max(dp[(i-2,j-1)]+a[i-1],dp[(i-1,j)])
print(dp[(n,n//2)])

N = int(input())
A = [int(x) for x in input().split()]

dp = [[0]*3]*N

dp[0][0] = 0  # ((i+1)-1)/2
dp[0][1] = 0 # (i+1)/2
dp[0][2] = A[0]  # ((i+1)+1)/2

for i in range(1, N):
    
    if i % 2 == 0:
        dp[i][0] = dp[i-1][0] + A[i]
        dp[i][1] = max(dp[i-1][1], dp[i-1][2])
        dp[i][2] = dp[i-1][2] + A[i]
    else:
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = dp[i-1][1] + A[i]
        dp[i][2] = dp[i-1][2]

if N % 2 == 0:
    print(max(dp[N-1][1],dp[N-1][2]))
else:
    print(max(dp[N-1][0],dp[N-1][1]))

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = list(map(int, read().split()))

    skip = 1 + N % 2
    dp = [[-INF] * (skip + 1) for _ in range(N + 2)]
    dp[0][0] = 0

    for i in range(N + 1):
        for j in range(skip + 1):
            if j < skip and dp[i + 1][j + 1] < dp[i][j]:
                dp[i + 1][j + 1] = dp[i][j]
            if i < N and dp[i + 2][j] < dp[i][j] + A[i]:
                dp[i + 2][j] = dp[i][j] + A[i]

    print((dp[N + 1][skip]))

    return


def __starting_point():
    main()

__starting_point()

N = int(input())
num = list(map(int, input().split()))
dp_odd = [0, num[0]]
dp_even = max(num[0], num[1])
for i in range(2, N):
  if (i + 1) % 2 == 1:
    dp_odd = [max(dp_odd[0] + num[i], dp_even), dp_odd[1] + num[i]]
  else:
    dp_even = max(dp_even + num[i], dp_odd[1])

if N % 2 == 0:
  print(dp_even)
else:
  print(dp_odd[0])

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = list(map(int, read().split()))

    dp_used = [[-INF] * 2 for _ in range(N + 1)]
    dp_unused = [[-INF] * 2 for _ in range(N + 1)]

    dp_used[0][1] = dp_unused[0][1] = 0

    for i in range(N):
        if i % 2 == 0:
            dp_unused[i + 1][0] = max(dp_used[i][1], dp_unused[i][1])
            dp_used[i + 1][0] = dp_unused[i][0] + A[i]
            dp_used[i + 1][1] = dp_unused[i][1] + A[i]
        else:
            dp_unused[i + 1][0] = max(dp_unused[i][0], dp_used[i][0])
            dp_unused[i + 1][1] = dp_used[i][1]
            dp_used[i + 1][1] = dp_unused[i][0] + A[i]

    if N % 2 == 0:
        print((max(dp_unused[N][1], dp_used[N][1])))
    else:
        print((max(dp_unused[N][0], dp_used[N][0])))

    return


def __starting_point():
    main()

__starting_point()

import collections, sys
sys.setrecursionlimit(100005)
N = int(input())
A = [int(_) for _ in input().split()]
INF = float('inf')
memo = collections.defaultdict(lambda: INF)


def c(start, res):
    if memo[start, res] != INF:
        return memo[start, res]
    elif 2 * res - 1 > N - start:
        memo[start, res] = -INF
    elif start >= N:
        memo[start, res] = -INF
    elif res > 1:
        memo[start, res] = max(A[start] + c(start + 2, res - 1),
                               c(start + 1, res), c(start + 2, res))
    else:
        memo[start, res] = max(A[start], c(start + 1, res))
    return memo[start, res]


print((c(0, N // 2)))


import sys
#import copy
#import numpy as np
#import itertools
#import collections
#from collections import deque
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

inf = float('inf')
#inf = pow(10, 10)

def main():
    # input
    N = int(readline())
    A = list(map(int, readline().split()))

    K = N//2
    DP0 = [-inf] * N
    DP1 = [-inf] * N
    DP2 = [-inf] * N

    DP2[0] = A[0]
    DP2[1] = max(A[0], A[1])
    DP1[:2] = [0] * 2
    DP0[:4] = [0] * 4
    for i in range(2, N):
        if i%2 == 0:
            DP2[i] = DP2[i-2] + A[i]
            DP1[i] = max(DP2[i-1], DP1[i-2] + A[i])
            DP0[i] = max(DP1[i-1], DP0[i-2] + A[i])
        else:
            DP2[i] = max(DP2[i-2] + A[i], DP2[i-1])
            DP1[i] = max(DP1[i-1], DP1[i-2] + A[i])
            DP0[i] = max(DP0[i-1], DP0[i-2] + A[i])

    if N%2 == 0:
        ans = DP2[N-1]
    else:
        ans = DP1[N-1]

    #print(DP0)
    #print(DP1)
    #print(DP2)
    print(ans)


def __starting_point():
    main()

__starting_point()


def resolve():
    INF = float("-inf")
    N = int(input())
    A = list(map(int, input().split()))

    skip = 1 + N % 2
    # i番目までの要素を見たときに、ｊ個選ばない時の最大値
    dp = [[INF] * (skip + 2) for _ in range(N + 1)]
    dp[0][0] = 0

    for i in range(N):
        for j in range(skip + 1):  # j: スキップする個数
            # 今見ている要素をスキップ
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
            now = dp[i][j]
            if (i + j) % 2 == 0:
                now += A[i]
            dp[i + 1][j] = max(dp[i + 1][j], now)

    print(dp[N][skip])


def __starting_point():
    resolve()
__starting_point()

n=int(input())
l=list(map(int,input().split()))
m=n//2
t=n%2+2
dp=[0]*t
for i in range(m):
    for j in range(t):
        dp[j]+=l[2*i+j]
    for j in range(1,t):
        dp[j]=max(dp[j],dp[j-1])
print(dp[-1])

import sys
input=lambda :sys.stdin.readline().rstrip()

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

k = 1+n%2
f_inf = float('inf')

dp = [[-f_inf for _ in range(4)] for _ in range(200005)]
dp[0][0] = 0
for i in range(n):
    for j in range(k+1):
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])
        now = dp[i][j]
        if (i+j)%2 == 0: now += A[i]
        dp[i+1][j] = max(dp[i+1][j], now)

ans = dp[n][k]
print(ans)

# coding: utf-8
#import numpy as np
inf = float('inf')

def main():
    # input
    N = int(input())
    A = [0] + list(map(int, input().split()))
#    N = 2*10**5-1
#    A = [0] + np.random.randint(-10**9, 10**9, 2*10**5-1).tolist()

    dp1 = [-inf] * (N+1)
    dp2 = [-inf] * (N+1)
    dp1[1] = 0
    dp2[1] = 0
    dp1[2] = A[1]
    dp2[2] = A[2]
    for i in range(3, N+1):
        if i%2 == 0:
            dp1[i] = dp1[i-2] + A[i-1]
            dp2[i] = max(dp2[i-2] + A[i], dp1[i-2] + A[i])
        else:
            dp1[i] = max(dp2[i-1], dp1[i-2]+A[i-1])
            dp2[i] = max(dp2[i-2] + A[i], dp1[i-2] + A[i])

    if N % 2 == 0:
        ans = max([dp1[N], dp2[N]])
    else:
        ans = max(dp1[-2:] + dp2[-2:])

    # print(DP0)
    # print(DP1)
    # print(DP2)
    print(ans)


def __starting_point():
    main()
__starting_point()

n=int(input())
a=list(map(int,input().split()))
import numpy as np
dp=np.full((3,n+1),-pow(10,15))
dp[:,0]=0
dp[1,1]=a[0]
for i in range(2,n+1):
    #l,r=max(1,n//2-(n-i+1)//2),(i+1)//2+1
    l,r=max(1,i//2-1),(i+1)//2+1
    if i%3==2:
        now,pre,prepre=2,1,0
    elif i%3==0:
        now,pre,prepre=0,2,1
    elif i%3==1:
        now,pre,prepre=1,0,2
    dp[now,l:r]=np.maximum(dp[pre,l:r],dp[prepre,l-1:r-1]+a[i-1])
print(dp[now,n//2])

n = int(input())
A = list(map(int,input().split()))
if n%2==0:
    ans1=A[0];ans2=A[1]
    for i in range((n-2)//2):
        ans2 = max(ans1,ans2)+A[(i+1)*2+1]
        ans1 = ans1++A[(i+1)*2]
    print(max([ans1,ans2]))

else:
    ans1,ans2,ans3,=A[0],A[1],A[2]
    for i in range((n-2)//2):
        ans3 = max(ans3,ans2) + A[(i+2)*2]
        ans2 = max(ans1,ans2) + A[(i+2)*2-1]
        ans1 = ans1 + A[(i+1)*2]
    print(max([ans1,ans2,ans3]))

N = int(input())
A = list(map(int, input().split()))
dp = [[-10**20 for i in range(3)] for j in range(N+1)]
dp[0][1] = 0
dp[1][1] = 0
dp[1][2] = A[0]

for i in range(1, N):
    if i % 2 == 0:
        dp[i+1][0] = max(dp[i-1][0]+A[i], dp[i][0])
        dp[i+1][1] = max(dp[i-1][1]+A[i], dp[i][1])
        dp[i+1][2] = dp[i-1][2]+A[i]
    else:
        dp[i+1][0] = max(dp[i-1][0]+A[i], dp[i][1])
        dp[i+1][1] = max(dp[i-1][1]+A[i], dp[i][2])
        dp[i+1][2] = dp[i-1][2]+A[i]
ans = dp[N][1]
print(ans)

from collections import defaultdict

N = int(input())
*A, = list(map(int, input().split()))
INF = 10**20
dp = defaultdict(lambda :-INF)
dp[(0,0,0)] = 0

for i in range(1, N+1):
    for j in range(i//2-1, i//2+2):
        dp[1,i,j] = dp[0,i-1,j-1]+A[i-1]
        dp[0,i,j] = max(dp[1,i-1,j], dp[0,i-1,j])

ans = max(dp[1,N,N//2], dp[0,N,N//2])
print(ans)


N = int(input())
A = list(map(int, input().split()))

DP_odd = [0, A[0]]
DP_even = [0, max(A[0], A[1])]

for i in range(2, N):
    if (i + 1) % 2 == 1:    
        DP_odd = [max(DP_odd[0] + A[i], DP_even[1]), DP_odd[1] + A[i]]
    else:
        DP_even = [max(DP_even[0] + A[i], DP_odd[0]), max(DP_even[1] + A[i], DP_odd[1])]

if N % 2 == 1:
    ans = DP_odd[0]
else:
    ans = DP_even[1]

print(ans)

N = int(input())
A = list(map(int,input().split()))
odds_or_even = N%2+2
inf = -float("inf")
dp = [[inf for _ in range(N+1)] for _ in range(odds_or_even)]
dp[0][0] = 0
for i in range(N):
    dp[0][i+1] = dp[0][i]+A[i]*((i+1)%2)
for j in range(1,odds_or_even):
    for i in range(N):
        dp[j][i+1] = max(dp[j-1][i],dp[j][i]+A[i]*((i+j+1)%2))

print(dp[odds_or_even-1][N])

n = int(input())
a = [int(i) for i in input().split()]
k = 1 + n%2
dp = [[-float('inf')] * (k + 2) for i in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(k + 1):
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
        now = dp[i][j]
        if (i + j) % 2 == 0:
            now += a[i]
        dp[i + 1][j] = max(dp[i + 1][j], now)
print(dp[n][k])

N = int(input())
K = N % 2 + 1
A = tuple(map(int, input().split()))
table = [[-float("inf")] * (K + 2) for _ in range(N + 1)]
table[0][0] = 0
for i in range(N):
    for j in range(K + 1):
        table[i + 1][j] = max(table[i][j] + (A[i] if not (i + j) % 2 else 0), table[i + 1][j])
        table[i + 1][j + 1] = max(table[i][j], table[i + 1][j + 1])
print((table[N][K]))


# F - Select Half
N = int(input())
A = list(map(int,input().split()))

if N%2==0:
    rec = [[0]*N for _ in range(2)]
    rec[0][0] = A[0]
    rec[1][1] = A[1]
    for i in range(2,N):
        rec[0][i] = rec[0][i-2]+A[i]
        rec[1][i] = max(rec[0][i-3],rec[1][i-2])+A[i]
    ans = max(rec[0][N-2],rec[1][N-1])
else:
    rec = [[0]*N for _ in range(3)]
    rec[0][0] = A[0]
    rec[1][1] = A[1]
    rec[0][2] = A[0]+A[2]
    rec[2][2] = A[2]
    for i in range(3,N):
        rec[0][i] = rec[0][i-2]+A[i]
        rec[1][i] = max(rec[0][i-3],rec[1][i-2])+A[i]
        rec[2][i] = max(rec[0][i-4],rec[1][i-3],rec[2][i-2])+A[i]
    ans = max(rec[0][N-3],rec[1][N-2],rec[2][N-1])
    
print(ans)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[[-float("inf")]*2 for j in range(3)] for i in range(n+1)]
    #dp[index][i//2+j個選んだ][直前の値を採用したか否か]
    dp[0][0][0] = 0
    for i in range(n):
        x = a[i]
        if i%2 == 0:
            for j in range(-1, 2):
                dp[i+1][j][0] = max(dp[i][j][0], dp[i][j][1])
            for j in range(-1, 1):
                dp[i+1][j+1][1] = dp[i][j][0] + x
        else:
            for j in range(-1, 1):
                dp[i+1][j][0] = max(dp[i][j+1][0], dp[i][j+1][1])
            for j in range(-1, 2):
                dp[i+1][j][1] = dp[i][j][0] + x
    print(max(dp[n][0][0], dp[n][0][1]))

def __starting_point():
    main()
__starting_point()

from collections import defaultdict

INF = float("inf")

N, *A = map(int, open(0).read().split())

dp_in = defaultdict(lambda: -INF)

dp_out = defaultdict(lambda: -INF)
dp_out[(0, 0)] = 0

for i, a in enumerate(A, 1):
    p = i // 2
    for j in [p - 1, p, p + 1]:
        dp_in[(i, j)] = a + dp_out[(i - 1, j - 1)]
        dp_out[(i, j)] = max(dp_in[(i - 1, j)], dp_out[(i - 1, j)])

print(max(dp_in[(N, N // 2)], dp_out[(N, N // 2)]))

from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))
m = n//2
INF = 10**18
dp = [defaultdict(lambda: -INF) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(i//2-1, (i+1)//2+1):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i-1])
        elif 0 <= i-2 and 0 <= j <= m:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+A[i-1])
print(dp[-1][m])

def main():
    from functools import lru_cache
    import sys

    sys.setrecursionlimit(10 ** 7)

    inf = 2 * 10 ** 14 + 1

    N = int(input())
    *a, = list(map(int, input().split()))

    @lru_cache(maxsize=None)
    def recursion(cur, need):
        """
        cur: pickableなindex
        """
        if cur >= N:
            if need == 0:
                return 0
            else:
                return -inf

        rest = N - cur
        if (rest + 1) // 2 < need:
            return -inf

        return max(
            a[cur] + recursion(cur + 2, need - 1),
            recursion(cur + 1, need)
        )

    ans = recursion(0, N // 2)

    print(ans)


def __starting_point():
    main()

__starting_point()

import numpy as np
import itertools

N = int(input())
A = list(map(int, input().split()))

if N%2==0:
    left = np.cumsum([0]+A[::2])
    right = np.cumsum([0]+A[::-2])[::-1]
    ans = max(left+right)
else:
    left = np.cumsum([0] + A[:-1:2])
    mid_left = np.cumsum([0]+A[-2::-2])[::-1]
    mid_right = np.cumsum([0]+A[1::2])
    right = np.cumsum([0] + A[:1:-2])[::-1]

    left_sum = left+mid_left
    left_max = np.zeros(N//2+1, dtype=int)
    left_max[0] = left_sum[0]
    for i in range(1, N//2+1):
        left_max[i] = max(left_max[i-1], left_sum[i])
    left_max -= mid_left

    right_sum = right + mid_right
    right_max = np.zeros(N//2 + 1, dtype=int)
    right_max[-1] = right_sum[-1]
    for i in range(N//2-1, -1, -1):
        right_max[i] = max(right_max[i + 1], right_sum[i])
    right_max -= mid_right

    ans = max(left_max+right_max)


print(ans)


import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
m=n//2
if n%2==0:
    dp=[[-10**18]*2 for _ in range(m)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    for i in range(1,m):
        for j in range(2*i,2*(i+1)):
            for k in range(2*(i-1),2*i):
                if j-k>1:
                    dp[i][j%2]=max(dp[i][j%2],dp[i-1][k%2]+a[j])
else:
    dp=[[-10**18]*3 for _ in range(m)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    dp[0][2]=a[2]
    for i in range(1,m):
        for j in range(2*i,2*(i+1)+1):
            for k in range(2*(i-1),2*i+1):
                if j-k>1:
                    dp[i][j-2*i]=max(dp[i][j-2*i],dp[i-1][k-2*(i-1)]+a[j])
print(max(dp[-1]))

def get_next_unchosen(current , chooseNum):
    if (chooseNum , 0) in current or (chooseNum , 1) in current:
        if (chooseNum , 0) in current and (chooseNum ,1) in current:
            return max(current[(chooseNum, 0)] , current[(chooseNum, 1)])
        if (chooseNum , 0) in current:
            return current[(chooseNum , 0)]
        return current[(chooseNum,1)]
    return None


def calc_next_state(current, must_choose_num, a):
    next = {}
    current_unchosen_nums = [choose_num  for (choose_num, prev_chosen) in list(current.keys()) if prev_chosen == 0 and choose_num >= must_choose_num - 1]
    for chooseNum in current_unchosen_nums:
        next[(chooseNum + 1, 1)] = current[(chooseNum , 0)] + a
    for chooseNum in range(must_choose_num, N):
        n = get_next_unchosen(current, chooseNum)
        if n is None:
            break
        else:
            next[(chooseNum , 0)] = n
    return next


N = int(input())
A = [int(x) for x in input().split()]

totalChooseNum = N // 2
dp = {(0, 0) : 0}
for i in range(0, N):
    ai = A[i]
    canChooseNum = (N - i + 1) // 2
    mustChooseNum = max(totalChooseNum - canChooseNum, 0)
    dp = calc_next_state(dp, mustChooseNum, ai)

result = max(dp[(totalChooseNum, 0)] , dp[(totalChooseNum , 1)])
print(result)


from collections import defaultdict

def main():
    INF = float("inf")

    N, *A = map(int, open(0).read().split())

    dp_in = defaultdict(lambda: -INF)

    dp_out = defaultdict(lambda: -INF)
    dp_out[(0, 0)] = 0

    for i, a in enumerate(A, 1):
        p = i // 2
        for j in [p - 1, p, p + 1]:
            dp_in[(i, j)] = a + dp_out[(i - 1, j - 1)]
            dp_out[(i, j)] = max(dp_in[(i - 1, j)], dp_out[(i - 1, j)])

    print(max(dp_in[(N, N // 2)], dp_out[(N, N // 2)]))

main()

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

# dp[i][k] 列iを選択し、k個持っているときの最大値
# kは(i-1)//2 or i//2 or (i+1)//2
# それぞれki=0,1,2とする。
# 最大でも4マス前まで(oxxxo)
# iが奇数
# dp[i+2][0]=Ai + max(dp[i][0], dp[i][1], dp[i-1][1],  dp[i-2][2])
# dp[i+2][1]=dp[i+2][0]
# dp[i+2][2]=Ai + max(dp[i][2])
# iが偶数
# dp[i+2][0]=0
# dp[i+2][1]=Ai + max(dp[i][1], dp[i][2], dp[i-1][2])
# dp[i+2][2]=dp[i+2][1]

dp = [[0 for i in range(3)] for j in range(n)]
ans = 0

dp[0][2] = a[0]
ans = dp[0][2]
dp[1][0] = 0
dp[1][1] = a[1]
dp[1][2] = a[1]
ans = max([ans, dp[1][1]])

if n == 2:
    print(ans)
else:
    for i in range(2, n):
        if (i + 1) % 2 == 0:
            dp[i][0] = 0
            dp[i][1] = a[i] + max(dp[i - 2][1], dp[i - 3][2])
            dp[i][2] = dp[i][1]
        else:
            if i > 2:
                dp[i][0] = a[i] + max(dp[i - 2][0], dp[i - 3][1], dp[i - 4][2])
            else:
                dp[i][0] = a[i] + dp[i - 2][0]
            dp[i][1] = dp[i][0]
            dp[i][2] = a[i] + dp[i - 2][2]
        
    if n % 2 == 0:
        print(max(dp[-1][1],dp[-2][2]))
    else:
        print(max(dp[-1][0],dp[-2][1],dp[-3][2]))

from collections import defaultdict

N = int(input())
A = list(map(int,input().split()))

DP = defaultdict(lambda: -10**18)

DP[(0,0)] = A[0]

for i in range(1,N):
    for j in range((i+1)//2-1,(i+2)//2):
        if j == 0:
            DP[(i,0)] = max(DP[(i-1,0)],A[i])
        else:
            DP[(i,j)] = max(DP[(i-1,j)],DP[(i-2,j-1)]+A[i])

print((DP[(N-1,N//2-1)]))


from collections import defaultdict
n=int(input())
a=[int(i) for i in input().split()]
INF=float('inf')
dp0=defaultdict(lambda: -INF)
dp1=defaultdict(lambda: -INF)
dp0[(0,0)]=0
for i in range(1,n+1):
  for j in range(i//2-1,(i+1)//2+1):
    dp0[(i,j)]=max(dp0[(i-1,j)],dp1[(i-1,j)])
    dp1[(i,j)]=dp0[(i-1,j-1)]+a[i-1]
print(max(dp0[(n,n//2)],dp1[(n,n//2)]))

P,M,A,I=input,max,int,-10**9
n,a=A(P()),list(map(A,P().split()))
x,y,z=0,I,I
for i,L in enumerate(a):
 if i%2:z=M(y,z);y+=L
 else:y=M(x,y);x+=L;z+=L
print(M(y,z)if n%2else M(x,y))

N = int(input())
A = list(map(int,input().split()))

DP = [0,0,0]
m = N//2*2
if N%2 == 0:
    for i in range(0,m,2):
        DP[0] += A[i]
        DP[1] += A[i+1]
        DP[1] = max(DP[0],DP[1])

    print((DP[1]))

else:
    for i in range(0,m,2):
        DP[0] += A[i]
        DP[1] += A[i+1]
        DP[2] += A[i+2]

        DP[1] = max(DP[0],DP[1])
        DP[2] = max(DP[1],DP[2])

    print((DP[2]))