AtCoder Beginner Contest 162 - Select Half

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: MEDIUM

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
dp = [0]
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])


N = int(input())
A = [int(x) for x in input().split()]
dp = [[0] * 3] * N
dp[0][0] = 0
dp[0][1] = 0
dp[0][2] = A[0]
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]))


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])


n = int(input())
a = [int(x) for x in input().split()]
dp00 = -10 ** 9
dp01 = 0
dp10 = -10 ** 9
dp11 = 0
for i in range(n):
	if i % 2 == 0:
		dp10 = dp00 + a[i]
		dp00 = max(dp01, dp11)
		dp11 = dp01 + a[i]
	else:
		dp01 = dp11
		dp11 = dp00 + a[i]
		dp00 = max(dp00, dp10)
		if i == 3:
			dp10 = a[i]
if n % 2 == 0:
	print(max(dp01, dp11))
else:
	print(max(dp00, dp10))


N = int(input())
A = list(map(int, input().split()))
B = [[0] * 2 for i in range(300000)]
for i in range(N):
	if i == 0:
		B[0][0] = 0
		B[0][1] = A[0]
	elif i == 1:
		B[1][0] = 0
		B[1][1] = max([A[0], A[1]])
	elif i % 2 == 0:
		B[i][0] = max([B[i - 2][0] + A[i], B[i - 1][1]])
		B[i][1] = B[i - 2][1] + A[i]
	else:
		B[i][0] = max([B[i - 2][0] + A[i], B[i - 1][0]])
		B[i][1] = max([B[i - 2][1] + A[i], B[i - 1][1]])
if i % 2 == 0:
	print(B[N - 1][0])
else:
	print(B[N - 1][1])


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()))
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)


def main():
	from collections import defaultdict
	inf = 10 ** 15
	N = int(input())
	(*a,) = map(int, input().split())
	it = iter(a)
	dp = [defaultdict(lambda : -inf) for _ in range(N + 1)]
	dp[0][0] = 0
	dp[1][0] = 0
	dp[1][1] = next(it)
	for (i, x) in enumerate(it, 2):
		mi = (i - 1) // 2
		ma = (i + 1) // 2
		for taken_count in range(mi, ma + 1):
			dp[i][taken_count] = max(dp[i - 1][taken_count], dp[i - 2][taken_count - 1] + x)
	ans = dp[N][N // 2]
	print(ans)
main()


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


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


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])


n = int(input())
a = list(map(int, input().split()))
INF = 1001001001001001
c = n // 2
dp = [[-INF] * 3 for _ in range(c + 1)]
dp[0][0] = 0
for i in range(c + 1):
	for j in range(3):
		for k in range(3):
			if i + 1 <= c and j + k < 3 and (2 * i + j + k < n):
				dp[i + 1][j + k] = max(dp[i + 1][j + k], dp[i][j] + a[2 * i + j + k])
ans = -INF
for i in range(3):
	ans = max(ans, dp[c][i])
print(ans)


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()))
C = [0 for _ in range(N)]
D = [0 for _ in range(N)]
E = [0 for _ in range(N)]
E[0] = a[0]
for i in range(1, N):
	if i % 2 == 0:
		C[i] = max(C[i - 2] + a[i], D[i - 1])
		E[i] = E[i - 2] + a[i]
	else:
		D[i] = max(D[i - 2] + a[i], E[i - 1])
if N % 2 == 0:
	print(D[N - 1])
else:
	print(C[N - 1])


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]))


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


import sys
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
from collections import defaultdict

def resolve():
	N = ir()
	A = lr()
	dp = defaultdict(lambda : -float('inf'))
	dp[0, 0, 0] = 0
	for i in range(N):
		for j in range(max(i // 2 - 1, 0), i // 2 + 2):
			dp[i + 1, j + 1, 1] = dp[i, j, 0] + A[i]
			dp[i + 1, j, 0] = max(dp[i, j, 0], dp[i, j, 1])
	print(max(dp[N, N // 2, 1], dp[N, N // 2, 0]))
resolve()


N = int(input())
A = list(map(int, input().split()))
if N % 2:
	a = [None] * N
	b = [None] * N
	c = [None] * N
	a[0] = A[0]
	b[1] = A[1]
	c[2] = A[2]
	for i in range(2, N - 2, 2):
		a[i] = a[i - 2] + A[i]
	for i in range(3, N, 2):
		b[i] = max(a[i - 3], b[i - 2]) + A[i]
	for i in range(4, N, 2):
		c[i] = max(a[i - 4], b[i - 3], c[i - 2]) + A[i]
	print(max(a[-3], b[-2], c[-1]))
else:
	a = [None] * N
	b = [None] * N
	a[0] = A[0]
	for i in range(2, N, 2):
		a[i] = a[i - 2] + A[i]
	b[1] = A[1]
	for i in range(3, N, 2):
		b[i] = max(a[i - 3], b[i - 2]) + A[i]
	print(max(a[-2], b[-1]))


N = int(input())
A = list(map(int, input().split()))
dp_g = A[1]
dp_k = A[0]
dp = [0, max(dp_g, dp_k)]
for i in range(2, N):
	if i % 2 == 1:
		dp_g = max(dp_k, dp_g) + A[i]
		dp_k += A[i - 1]
		dp.append(max(dp_g, dp_k))
	elif i % 2 == 0:
		dp.append(max(dp[i - 1], dp[i - 2] + A[i]))
print(dp[N - 1])


from itertools import accumulate
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
odd = list(accumulate([0] + A[::2]))
even = list(accumulate([0] + A[::-1][::2]))
ans = max((odd[i] + even[N // 2 - i] for i in range(N // 2 + 1)))
if N % 2 == 1:
	dp = [0] * (N // 2 + 1)
	for i in range(0, N - 1, 2):
		dp[i // 2 + 1] = max(odd[i // 2 + 1], dp[i // 2] + A[i + 1])
	ans2 = max((dp[i] + even[N // 2 - i] for i in range(N // 2 + 1)))
	ans = max(ans, ans2)
print(ans)


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])
main()


import sys
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
nn = lambda : list(stdin.readline().split())
ns = lambda : stdin.readline().rstrip()
n = ni()
a = na()
dp = [0] * n
b = a[0]
dp[1] = max(a[0], a[1])
for i in range(2, n):
	if i % 2 == 0:
		b += a[i]
		dp[i] = max(dp[i - 1], dp[i - 2] + a[i])
	else:
		dp[i] = max(b, dp[i - 2] + a[i])
print(dp[-1])


n = int(input())
nums = [int(s) for s in input().split()]
odds = [0]
for num in nums[::2]:
	odds.append(num + odds[-1])
res = [0]
for (i, num) in enumerate(nums[1::2]):
	res.append(max(res[-1] + num, odds[i + 1]))
if n % 2 == 0:
	print(res[-1])
else:
	ans = float('-inf')
	for (i, r) in enumerate(res):
		ans = max(ans, res[i] + odds[-1] - odds[i + 1])
	print(ans)


N = int(input())
A = list(map(int, input().split()))
dp = [{} for _ in range(N + 1)]
INF = -float('inf')
for i in range(1, N + 1):
	mid = i // 2
	(dp[i][mid - 2], dp[i][mid - 1], dp[i][mid], dp[i][mid + 1], dp[i][mid + 2]) = (INF, INF, INF, INF, INF)
dp[1][1] = A[0]
dp[2][1] = max(A[1], dp[1][1])
(dp[1][0], dp[2][0]) = (0, 0)
for i in range(2, N):
	a = A[i]
	ma = (i + 2) // 2
	mi = i // 2
	dp[i + 1][ma] = max(dp[i][ma], dp[i - 1][ma - 1] + a)
	dp[i + 1][mi] = max(dp[i][mi], dp[i - 1][mi - 1] + a)
print(dp[-1][N // 2])


import functools
import sys
sys.setrecursionlimit(1000000)
(N,) = (int(x) for x in input().split())
arr = [int(x) for x in input().split()]

@functools.lru_cache(None)
def dp(i, k):
	if k <= 0:
		return 0
	rem = N - i
	if k > rem // 2 + rem % 2:
		return -float('inf')
	return max(arr[i] + dp(i + 2, k - 1), dp(i + 1, k))
sol = dp(0, N // 2)
print(sol)


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()


n = int(input())
A = list(map(int, input().split()))
INF = 10 ** 18
dp_use = [-INF] * 5
dp_not_use = [-INF] * 5
dp_not_use[0] = 0
for a in A:
	tmp_use = [-INF] * 5
	tmp_not_use = [-INF] * 5
	for current_dif in range(-3, 2):
		if current_dif - 1 >= -3:
			tmp_use[current_dif] = dp_not_use[current_dif - 1] + a
		if current_dif + 1 < 2:
			tmp_not_use[current_dif] = max(dp_use[current_dif + 1], dp_not_use[current_dif + 1])
	dp_use = tmp_use
	dp_not_use = tmp_not_use
dif = n // 2 - (n - n // 2)
print(max(dp_use[dif], dp_not_use[dif]))


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[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 = int(input())
A = list(map(int, input().split()))
k = 1 + N % 2
INF = 10 ** 18
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])
		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])


import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
N = ir()
A = lr()
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
	if index >= N:
		return -INF
	if N - index + 1 < 2 * n:
		return -INF
	if N - index - 2 > 2 * n:
		return -INF
	if n == 0:
		return 0
	elif n == 1:
		return max(A[index:])
	ret = max(A[index] + F(index + 2, n - 1), F(index + 1, n))
	return ret
answer = F(0, N // 2)
print(answer)


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[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()


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())
a = tuple(map(int, input().split()))
if n <= 3:
	print(max(a))
	exit()
dp = [[0] * 2 for _ in range(n + 1)]
dp[1][1] = a[0]
dp[2][1] = a[1]
dp[3][0] = a[2]
dp[3][1] = a[0] + a[2]
for i in range(4, n + 1):
	if i % 2 == 0:
		dp[i][1] = a[i - 1] + max(dp[i - 2][1], dp[i - 3][1])
	else:
		dp[i][0] = a[i - 1] + max(dp[i - 2][0], dp[i - 3][1], dp[i - 4][1])
		dp[i][1] = a[i - 1] + dp[i - 2][1]
if n % 2 == 0:
	ans = max(dp[-1][1], dp[-2][1])
else:
	ans = max(dp[-1][0], dp[-2][1], dp[-3][1])
print(ans)


n = int(input())
a = [int(ai) for ai in input().split()]
if n % 2 == 0:
	s = [0, 0]
	for i in range(n // 2):
		s = [max((s[q] for q in range(p + 1))) + a[i * 2 + p] for p in range(2)]
	print(max(s))
else:
	s = [0, 0, 0]
	for i in range(n // 2):
		s = [max((s[q] for q in range(p + 1))) + a[i * 2 + p] for p in range(3)]
	print(max(s))


inf = float('inf')

def main():
	N = int(input())
	A = [0] + list(map(int, input().split()))
	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(ans)

def __starting_point():
	main()
__starting_point()


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])


n = int(input())
a = [int(j) for j in input().split()]
p = [0] * n
d = [0] * n
for i in range(n):
	p[i] = a[i] + p[i - 2]
	if i & 1:
		d[i] = max(p[i - 1], a[i] + d[i - 2])
	else:
		d[i] = max(d[i - 1], a[i] + d[i - 2])
print(d[-1])


import sys
readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
if N % 2 == 0:
	dp = [[0, 0] for i in range(N)]
	dp[1] = [A[0], A[1]]
	for i in range(3, N, 2):
		dp[i][0] = dp[i - 2][0] + A[i - 1]
		dp[i][1] = max(dp[i - 2][0] + A[i], dp[i - 2][1] + A[i])
	print(max(dp[N - 1]))
else:
	dp = [[0, 0, 0] for i in range(N)]
	dp[0] = [A[0], 0, 0]
	for i in range(2, N, 2):
		dp[i][0] = dp[i - 2][0] + A[i]
		dp[i][1] = max(dp[i - 2][0], dp[i - 2][1] + A[i - 1])
		dp[i][2] = max(dp[i - 2][1] + A[i], dp[i - 2][2] + A[i])
	print(max(dp[N - 1]))


INF = 10 ** 15
N = int(input())
As = list(map(int, input().split()))
As.append(-INF)
INF = 10 ** 15
dp = [[-INF] * (N // 2) for _ in range(3)]
dp[0][0] = As[0]
dp[1][0] = As[1]
dp[2][0] = As[2]
for i in range(1, N // 2):
	dp[0][i] = dp[0][i - 1] + As[2 * i]
	dp[1][i] = max(dp[0][i - 1], dp[1][i - 1]) + As[2 * i + 1]
	dp[2][i] = max(dp[0][i - 1], dp[1][i - 1], dp[2][i - 1]) + As[2 * i + 2]
if N % 2 == 0:
	print(max(dp[0][-1], dp[1][-1]))
else:
	print(max(dp[0][-1], dp[1][-1], dp[2][-1]))


n = int(input())
A = list(map(int, input().split()))
m = -10 ** 15
dp1 = [[m, m, m] for i in range(n)]
dp0 = [[m, m, m] for i in range(n)]
dp1[0][0] = A[0]
dp0[0][1] = 0
for i in range(1, n):
	for j in range(3):
		dp1[i][j] = max(dp1[i][j], dp0[i - 1][j] + A[i])
		dp0[i][j] = max(dp0[i][j], dp1[i - 1][j])
		if j != 2:
			dp0[i][j + 1] = max(dp0[i][j + 1], dp0[i - 1][j])
if n % 2 == 0:
	print(max(dp1[n - 1][1], dp0[n - 1][0]))
else:
	print(max(dp1[n - 1][2], dp0[n - 1][1]))


import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
if n <= 3:
	print(max(a))
	exit()
a = tuple(a)
dp = [[-10 ** 15] * 3 for i in range(n)]
dp[0][2] = a[0]
dp[1][2] = a[1]
dp[2][2] = a[0] + a[2]
dp[3][2] = max(a[0], a[1]) + a[3]
dp[3][1] = a[0] + a[3]
for i in range(2, n - 2):
	if i % 2 == 0:
		dp[i + 2][2] = dp[i][2] + a[i + 2]
		dp[i + 2][0] = max(dp[i][0] + a[i + 2], dp[i - 1][1] + a[i + 2], dp[i - 2][2] + a[i + 2])
	else:
		dp[i + 2][2] = max(dp[i][2], dp[i][1], dp[i - 1][2]) + a[i + 2]
	dp[i + 2][1] = max(dp[i][1] + a[i + 2], dp[i - 1][2] + a[i + 2])
if n % 2 == 1:
	c = min(a[0], a[-1])
	dp[n - 1][2] -= c
print(max(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]))


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]))


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()


import sys
sys.setrecursionlimit(10 ** 6)

def find(idx, c, arr, tb):
	if c == 0:
		return 0
	if idx <= 0 or idx < 2 * c - 1:
		return float('-inf')
	if (idx, c) in tb:
		return tb[idx, c]
	rs = find(idx - 2, c - 1, arr, tb) + arr[idx - 1]
	rs = max(rs, find(idx - 1, c, arr, tb))
	tb[idx, c] = rs
	return rs

def main():
	n = int(input())
	arr = [int(e) for e in input().split(' ')]
	print(find(n, n // 2, arr, {}))
	return 0
main()


from collections import defaultdict
INF = 2 ** 60
dp = defaultdict(lambda : -INF)
n = int(input())
a = list(map(int, input().split())) + [0] * 10
dp[0, 0] = 0
dp[1, 1] = a[0]
for i in range(n):
	for j in range(i // 2 - 2, i // 2 + 3):
		dp[i + 2, j + 1] = max([dp[i + 2, j + 1], dp[i, j] + a[i + 1]])
		dp[i + 1, j] = max([dp[i + 1, j], dp[i, j]])
print(dp[n, n // 2])


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


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
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])))


def main():
	N = int(input())
	A = list(map(int, input().split()))
	(a0, a1, a2, b0, b1, b2) = (0, 0, 0, 0, 0, 0)
	for (i, a) in enumerate(A):
		(a0, a1, a2, b0, b1, b2) = (b0, max(b1, a0), max(b2, a1), a0 + a, a1 + a if i >= 1 else a1, a2 + a if i >= 2 else a2)
	if N & 1:
		return max(b2, a1)
	else:
		return max(b1, a0)
print(main())


N = int(input())
A = list(map(int, input().split()))
INF = 10 ** 18
dp0 = [-INF] * (N + 2)
dp1 = [-INF] * (N + 2)
dp2 = [-INF] * (N + 2)
dp0[0] = 0
dp0[1] = 0
dp1[0] = 0
dp1[1] = 0
for (i, a) in enumerate(A, start=2):
	dp0[i] = dp0[i - 2] + a
	dp1[i] = max(dp1[i - 2] + a, dp0[i - 1])
	dp2[i] = max(dp2[i - 2] + a, dp1[i - 1], dp0[i - 2])
if N % 2 == 1:
	print(dp2[-1])
else:
	print(max(dp1[-1], dp0[-1]))


N = int(input()) + 2
X = [0, 0] + list(map(int, input().split()))
dp = [[0, 0] for _ in range(N)]
for i in range(2, N):
	if i % 2:
		dp[i][1] = max(dp[i - 2][1] + X[i], dp[i - 1][1])
		if i != 3:
			dp[i][0] = max(dp[i - 2][0] + X[i], dp[i - 1][0])
	else:
		dp[i][1] = dp[i - 2][1] + X[i]
		if i != 2:
			dp[i][0] = max(dp[i - 2][0] + X[i], dp[i - 1][1])
if N % 2:
	print(dp[-1][0])
else:
	print(dp[-1][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):
	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]))


n = int(input())
a = list(map(int, input().split()))
iseven = n % 2 == 0
if n == 2:
	print(max(a))
	exit()
dp = [[-float('inf') for _ in range(3)] for _ in range(n)]
dp[0][0] = a[0]
dp[1][1] = a[1]
if n > 2:
	dp[2][2] = a[2]
for i in range(n):
	for k in range(3):
		if i + 2 < n:
			dp[i + 2][k] = max(dp[i + 2][k], dp[i][k] + a[i + 2])
		if k <= 1 and i + 3 < n:
			dp[i + 3][k + 1] = max(dp[i + 3][k + 1], dp[i][k] + a[i + 3])
		if not iseven and k == 0 and (i + 4 < n):
			dp[i + 4][k + 2] = max(dp[i + 4][k + 2], dp[i][k] + a[i + 4])
if iseven:
	ans = max([dp[-1][0], dp[-1][1]])
else:
	ans = max([dp[-3][0], dp[-2][1], dp[-1][2]])
print(ans)


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)
		elif 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)


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])


N = int(input())
A = list(map(int, input().split()))
INF = 10 ** 18
dp = [[-INF for i in range(2)] for j in range(N + 1)]
dp[0][0] = 0
dp[1][0] = 0
dp[2][0] = 0
dp[1][1] = A[0]
dp[2][1] = A[1]
for i in range(3, N + 1):
	dp[i][0] = max(dp[i - 2][0] + A[i - 1], dp[i - 2][1])
	if i % 2 == 0:
		dp[i][0] = max(dp[i][0], dp[i - 3][0] + A[i - 1])
	else:
		dp[i][0] = max(dp[i][0], dp[i - 3][1] + A[i - 1])
	dp[i][1] = dp[i - 2][1] + A[i - 1]
	if i % 2 == 0:
		dp[i][1] = max(dp[i][1], dp[i - 3][1] + A[i - 1])
if N % 2 == 0:
	print(max(dp[N][1], dp[N - 1][1]))
else:
	print(max(dp[N][0], dp[N - 1][1], dp[N - 2][1]))


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


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])


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


N = int(input())
A = list(map(int, input().split()))
dp = [[0] * 4 for _ in range(200005)]
k = 1 + N % 2
for i in range(N + 1):
	for j in range(k + 1):
		dp[i][j] = -float('inf')
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)


from itertools import accumulate
(N, *A) = map(int, open(0).read().split())
INF = 1 << 60
dp = [[-INF] * 2 for _ in [0] * N]
dp[0][0] = 0
if N & 1:
	for (i, a) in enumerate(A):
		for j in range(i // 2 + 1, i // 2 - 1, -1):
			dp[j][0] = max(dp[j][0], dp[j][1])
			if j > 0:
				dp[j][1] = dp[j - 1][0] + a
else:
	for (i, a) in enumerate(A):
		for j in range(i // 2 + 1, (i + 1) // 2 - 1, -1):
			dp[j][0] = max(dp[j][0], dp[j][1])
			dp[j][1] = dp[j - 1][0] + a
print(max(dp[N // 2]))


n = int(input())
a = list(map(int, input().split()))
dp = [0 for i in range(3)]
for i in range(1, n + 1):
	ai = a[i - 1]
	if i % 2:
		dp[1] = max(dp[0], dp[1])
		dp[0] += ai
	if i % 2 == 0:
		dp[2] = max(dp[1], dp[2])
		dp[1] += ai
	if i >= 3 and i % 2:
		dp[2] += ai
if n % 2 == 0:
	print(max(dp[0], dp[1]))
else:
	print(max(dp[1], dp[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 % 2 else M(x, y))


N = int(input())
A = [int(hoge) for hoge in input().split()]
DP = [[0] * 3 for n in range(N)]
DP[0][0] = A[0]
for n in range(1, N):
	DP[n][0] = DP[n - 2][0] + A[n]
	DP[n][1] = max((DP[n - 2][1] + A[n], DP[n - 1][0]))
	DP[n][2] = max((DP[n - 2][2] + A[n], DP[n - 1][1]))
if N % 2:
	print(DP[n][2])
else:
	print(DP[n][1])


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]))


def resolve():
	INF = float('-inf')
	N = int(input())
	A = list(map(int, input().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:
				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])
	print(dp[N + 1][skip])

def __starting_point():
	resolve()
__starting_point()


N = int(input())
A = list(map(int, input().split()))
dp = [{} for _ in range(N + 2)]
dp[0][0] = 0
dp[-1][0] = 0
for i in range(1, N + 1):
	f = (i - 1) // 2
	t = (i + 1) // 2
	for j in range(f, t + 1):
		var1 = dp[i - 2][j - 1] + A[i - 1] if j - 1 in dp[i - 2] else -float('inf')
		var2 = dp[i - 1][j] if j in dp[i - 1] else -float('inf')
		dp[i][j] = max(var1, var2)
print(dp[N][N // 2])


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))


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, *l) = map(int, open(0).read().split())
p = [0, 0]
d = [0, 0]
i = 0
for l in l:
	d += (max(l + d[-2], [d, p][i & 1][-1]),)
	p += (l + p[-2],)
	i += 1
print(d[-1])


n = int(input())
a = list(map(int, input().split()))
m = 2 + n % 2
dp = [[-10 ** 18] * m for i in range(n + 2)]
dp[0][0] = 0
for i in range(n):
	for j in range(m):
		if i % 2 == j % 2:
			x = a[i]
		else:
			x = 0
		if dp[i + 1][j] < dp[i][j] + x:
			dp[i + 1][j] = dp[i][j] + x
		if j + 1 < m and dp[i + 1][j + 1] < dp[i][j]:
			dp[i + 1][j + 1] = dp[i][j]
print(max(dp[n][m - 2], dp[n][m - 1]))


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
K = 1 + N % 2
dp = [[-10 ** 18] * (K + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
	for j in range(K + 1):
		if j + 1 <= K:
			dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + (A[i] if (i + j) % 2 == 0 else 0))
print(dp[N][K])


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
dp = defaultdict(lambda : -pow(10, 18))
dp[1, 1] = a[0]
for i in range(2, n + 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, *A) = 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())
arr = list(map(int, input().split()))
if n <= 3:
	print(max(arr))
	exit()
lim = n % 2 + 2
dp = [[0] * lim for _ in range(n + 1)]
for i in range(n):
	dp[i + 1][0] = dp[i - 1][0] + arr[i]
	dp[i + 1][1] = max(dp[i - 1][1] + arr[i], dp[i - 2][0] + arr[i])
	if lim == 3:
		dp[i + 1][2] = max(dp[i - 1][2] + arr[i], dp[i - 2][1] + arr[i], dp[i - 3][0] + arr[i])
print(max(dp[-1][:lim]))


from math import gcd
from functools import reduce
n = int(input())
ar = list(map(int, input().split(' ')))
dp = [[-10 ** 20] * 6 for i in range(n + 5)] + [[0] + [-10 ** 20] * 8 for i in range(3)]

def cn(z, j):
	return (z - j + 1) // 2
ans = -10 ** 20
for i in range(n):
	idx = int(i)
	dp[idx] = dp[idx - 2].copy()
	for j in range(0, 5):
		for k in range(j + 1):
			dp[idx][j] = max(dp[idx][j], dp[idx - k - 2][j - k])
	for j in range(5):
		dp[i][j] += ar[i]
		if cn(i + 1, j) == n // 2:
			ans = max(ans, dp[i][j])
print(ans)


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])


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]))


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])


n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
	dmax = 0
	ans = sum(A[::2])
	d = [0] * (n // 2 + 1)
	for i in range(n // 2):
		d[i + 1] = d[i] + A[-2 * i - 1] - A[-2 * i - 2]
		dmax = max(dmax, d[i + 1])
	print(ans + dmax)
else:
	d1 = [0] * (n // 2 + 1)
	d1max = [0] * (n // 2 + 1)
	d2 = [0] * (n // 2 + 1)
	d2max = 0
	ans = sum(A[:-2:2])
	for i in range(n // 2):
		d1[i + 1] = d1[i] + A[-2 * i - 1] - A[-2 * i - 2]
		d1max[i + 1] = max(d1max[i], d1[i + 1])
		d2[i + 1] = d2[i] + A[-2 * i - 2] - A[-2 * i - 3]
		d2max = max(d2max, d2[i + 1] + d1max[i + 1])
	print(ans + d2max)


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])


n = int(input())
a = list(map(int, input().split()))
if n <= 3:
	print(max(a))
	exit()
if n & 1:
	dp = [3 * [-10 ** 20] for _ in range(n)]
	dp[0][0] = a[0]
	for i in range(1, n):
		if i % 2 == 0:
			dp[i][0] = dp[i - 2][0] + a[i]
			if i >= 3:
				dp[i][2] = max(dp[i - 2][2] + a[i], dp[i - 3][1] + a[i])
			else:
				dp[i][2] = a[i]
		elif i >= 3:
			dp[i][1] = max(dp[i - 2][1] + a[i], dp[i - 3][0] + a[i])
		else:
			dp[i][1] = a[i]
	print(max(dp[-1][2], dp[-2][1], dp[-3][0]))
else:
	b = [a[0]]
	c = [a[1]]
	for i in range(2, n):
		if i % 2 == 0:
			b.append(b[-1] + a[i])
		else:
			c.append(c[-1] + a[i])
	ans = max(b[-1], c[-1])
	for i in range(n // 2 - 1):
		ans = max(ans, b[i] + c[-1] - c[i])
	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 main():
	N = int(input())
	A = list(map(int, input().split()))
	dp = [[-1 * pow(10, 15)] * 3 for _ in range(N)]
	if N == 2:
		return max(A)
	dp[0][0] = A[0]
	dp[1][1] = A[1]
	dp[2][2] = A[2]
	for i in range(N):
		if i < 2:
			continue
		dp[i][0] = dp[i - 2][0] + A[i]
		if i < 3:
			continue
		dp[i][1] = max(dp[i - 3][0], dp[i - 2][1]) + A[i]
		if i < 4:
			continue
		dp[i][2] = max(dp[i - 4][0], dp[i - 3][1], dp[i - 2][2]) + A[i]
	if N % 2 == 0:
		return max(dp[-1][1], dp[-2][0])
	else:
		return max(dp[-1][2], dp[-2][1], dp[-3][0])
print(main())


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()))
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())
As = list(map(int, input().split()))
k = 0
k1 = As[0]
g = 0
for i in range(2, N + 1):
	if i % 2 == 1:
		k = max(k + As[i - 1], g)
		k1 = k1 + As[i - 1]
	if i % 2 == 0:
		g = max(k1, g + As[i - 1])
ans = g if N % 2 == 0 else k
print(ans)


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]))


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


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
readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
INF = 10 ** 18
limit = 4
S = 2 * limit + 3
dpb = [-INF] * S
dpw = [-INF] * S
dpw[0] = 0
for i in range(N):
	a = A[i]
	dpb2 = [-INF] * S
	dpw2 = [-INF] * S
	for j in range(-limit, limit):
		if -limit <= j - 1 < limit:
			dpw2[j - 1] = max(dpw2[j - 1], dpb[j], dpw[j])
			dpb2[j - 1] = max(dpb2[j - 1], dpb[j], dpw[j])
		if -limit <= j + 1 < limit:
			dpb2[j + 1] = max(dpb2[j + 1], dpw[j] + a)
	dpw = dpw2[:]
	dpb = dpb2[:]
idx = N // 2 * 2 - N
print(max(dpw[idx], dpb[idx]))


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))


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():
	N = int(input())
	A = [int(_) for _ in input().split()]
	dp = [[0, 0, 0] for _ in range(N // 2 + 1)]
	for i in range(N // 2):
		dp[i + 1][0] = dp[i][0] + A[i * 2]
		dp[i + 1][1] = max(dp[i][1], dp[i][0]) + A[i * 2 + 1]
		if N % 2:
			dp[i + 1][2] = max(dp[i][2], dp[i][1], dp[i][0]) + A[i * 2 + 2]
	if N % 2:
		print(max(dp[-1]))
	else:
		print(max(dp[-1][:2]))
main()


N = int(input())
A = list(map(int, input().split()))
from collections import deque
q = deque([(-1, 0, -2, 0)])
ans = -10 ** 18
for (i, a) in enumerate(A):
	d = {}
	while q and q[0][0] < i:
		(j, n, r, x) = q.popleft()
		if r < -1:
			if n == N // 2 - 1:
				ans = max(ans, x + a)
			elif n not in d:
				d[n] = x
			elif d[n] < x:
				d[n] = x
		if (j + 1) // 2 <= n:
			q.append((i, n, r - 1, x))
	for (n, x) in d.items():
		q.append((i, n + 1, -1, x + a))
print(ans)


n = int(input())
a = list(map(int, input().split()))
assert len(a) == n
memo = [{} for i in range(n)]
memo[0] = {0: 0, 1: a[0]}
memo[1] = {1: max(a[:2])}
for i in range(2, n):
	m = (i + 1) // 2
	memo[i][m] = max(memo[i - 1][m], memo[i - 2][m - 1] + a[i])
	if i % 2 == 0:
		memo[i][m + 1] = memo[i - 2][m] + a[i]
print(memo[-1][n // 2])


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 = int(input())
A = list(map(int, input().split()))
pick_DP = [-float('INF')] * n
unpick_DP = [-float('INF')] * n
pick_DP[0] = 0
unpick_DP[0] = 0
for (i, a) in enumerate(A, 1):
	mini = (i - 1) // 2 - 1
	if mini <= 0:
		mini = 1
	maxi = (i + 1) // 2
	temp = []
	for num in range(mini, maxi + 1):
		temp.append(pick_DP[num])
		pick_DP[num] = max(unpick_DP[num - 1] + a, pick_DP[num])
	for (num, pre_pick) in enumerate(temp, mini):
		if unpick_DP[num] < pre_pick:
			unpick_DP[num] = pre_pick
print(max(pick_DP[n // 2], unpick_DP[n // 2]))


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


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


n = int(input())
(*A,) = map(int, input().split())
inf = 10 ** 18
DP = [[-inf] * 2 for i in range(n)]
DP[0][0] = 0
DP[0][1] = A[0]
DP[1][0] = 0
DP[1][1] = max(A[0], A[1])
for i in range(2, n):
	if i % 2 == 0:
		DP[i][0] = max(DP[i - 2][0] + A[i], DP[i - 1][1])
		DP[i][1] = DP[i - 2][1] + A[i]
	else:
		DP[i][0] = max(DP[i - 2][0] + A[i], DP[i - 1][0])
		DP[i][1] = max(DP[i - 2][1] + A[i], DP[i - 1][1])
if n % 2 == 0:
	print(DP[n - 1][1])
else:
	print(DP[n - 1][0])


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)
if n % 2 == 0:
	print(max(x0, x1, o1))
else:
	print(max(x1, x2, o2))


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 sys import stdin, stdout

def main():
	N = int(stdin.readline())
	A = [0] + list(map(int, stdin.readline().rstrip().split()))
	dp = [0] * (N + 1)
	prefix = [0] * (N + 1)
	(dp[1], prefix[1]) = (0, A[1])
	for i in range(3, N, 2):
		prefix[i] = prefix[i - 2] + A[i]
	for i in range(2, N + 1):
		if i & 1:
			dp[i] = max(dp[i - 1], A[i] + dp[i - 2])
		else:
			dp[i] = max(dp[i - 2] + A[i], prefix[i - 1])
	stdout.write(str(dp[N]) + '\n')
main()


N = int(input())
A = list(map(int, input().split()))
if N % 2 == 0:
	S = [0] * N
	s = 0
	for i in range(0, N, 2):
		s += A[i]
		S[i] = s
	ans = s = sum(A[1:N:2])
	for t in range(1, N, 2):
		s -= A[t]
		ans = max(ans, S[t - 1] + s)
	print(ans)
else:
	S = [0] * N
	s = 0
	p = 0
	for t in range(2, N, 2):
		p += A[t - 2]
		S[t] = max(S[t - 2] + A[t - 1], p)
	ans = s = sum(A[2:N:2])
	for t in range(2, N, 2):
		s -= A[t]
		ans = max(ans, S[t] + s)
	print(ans)


n = int(input())
a = list(map(int, input().split()))
dp = [dict() for _ in range(n)]
dp[0][0] = 0
dp[0][1] = a[0]
dp[1][0] = 0
dp[1][1] = max(a[0], a[1])
import math
for i in range(2, n):
	k1 = int(math.ceil((i + 1) / 2))
	k2 = k1 - 1
	if i % 2 == 0:
		dp[i][k1] = dp[i - 2][k1 - 1] + a[i]
	else:
		dp[i][k1] = max(dp[i - 1][k1], dp[i - 2][k1 - 1] + a[i])
	dp[i][k2] = max(dp[i - 1][k2], dp[i - 2][k2 - 1] + a[i])
print(dp[-1][n // 2])


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]))


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


(N, *A) = map(int, open(0).read().split())
dp = [[-10 ** 10] * 3 for _ in range(N + 1)]
dp[0] = [0] * 3
dp[1][0] = A[0]
dp[2][1] = A[1]
for i in range(2, N):
	dp[i + 1][0] = dp[i - 1][0] + A[i]
	dp[i + 1][1] = max(dp[i - 1][1], dp[i - 2][0]) + A[i]
	dp[i + 1][2] = max(dp[i - 1][2], dp[i - 2][1], dp[i - 3][0]) + A[i]
if N % 2 == 1:
	print(max(dp[-3][0], dp[-2][1], dp[-1][2]))
else:
	print(max(dp[-2][0], dp[-1][1]))


import sys
sys.setrecursionlimit(10 ** 9)

def solve(pick, idx):
	if pick == 0:
		return 0
	if idx >= n:
		return -float('inf')
	if (pick, idx) in dp:
		return dp[pick, idx]
	if n - idx + 2 < pick * 2:
		return -float('inf')
	total = max(A[idx] + solve(pick - 1, idx + 2), solve(pick, idx + 1))
	dp[pick, idx] = total
	return total
n = int(input())
A = list(map(int, input().split()))
dp = {}
pick = n // 2
print(solve(pick, 0))


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


N = int(input())
A = list(map(int, input().split()))
dp = [0] * (N + 1)
dp[2] = max(A[0], A[1])
s = A[0]
for (i, a) in enumerate(A, 1):
	if i <= 2:
		continue
	if i % 2:
		dp[i] = max(dp[i - 1], a + dp[i - 2])
		s += a
	else:
		dp[i] = max(a + dp[i - 2], s)
print(dp[-1])


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])


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, 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])


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()


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


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]))


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())
l = list(map(int, input().split()))
p = [0] * n
d = [0] * n
p[0] = l[0]
for i in range(1, n):
	p[i] = l[i] + p[i - 2]
	d[i] = max(p[i - 1] if i & 1 else d[i - 1], l[i] + (d[i - 2] if i > 1 else 0))
print(d[-1])


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)


n = int(input())

def main():
	import sys
	input = sys.stdin.readline
	l = list(map(int, input().split()))
	dp = [[-float('INF')] * 3 for i in range(n + 1)]
	dp[0][0] = 0
	dp[1][-1] = 0
	dp[1][1] = l[0]
	for i in range(1, n):
		dp[i + 1][-1] = max(dp[i][0], dp[i - 1][-1] + l[i])
		dp[i + 1][0] = max(dp[i][1], dp[i - 1][0] + l[i])
		dp[i + 1][1] = dp[i - 1][1] + l[i]
	print(max(dp[-1][0], dp[-1][-1]))
main()


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)


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


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)


N = int(input())
A = [0] + list(map(int, input().split(' ')))
dp_list = [{0, 0}, {0: 0, 1: A[1]}, {0: 0, 1: A[1] if A[1] > A[2] else A[2]}]
for i in range(3, N + 1):
	b = (i - 1) // 2
	f = (i + 1) // 2
	dp_list.append({})
	for j in range(b, f + 1):
		if j in dp_list[i - 1]:
			dp_list[i][j] = dp_list[i - 2][j - 1] + A[i] if dp_list[i - 2][j - 1] + A[i] > dp_list[i - 1][j] else dp_list[i - 1][j]
		else:
			dp_list[i][j] = dp_list[i - 2][j - 1] + A[i]
print(dp_list[-1][N // 2])


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):
		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()


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


from collections import defaultdict

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

	def default():
		return -float('inf')
	dp = [defaultdict(default) for _ in range(N)]
	dp[0][0] = 0
	dp[0][1] = A[0]
	dp[1][0] = 0
	dp[1][1] = max(A[0], A[1])
	for i in range(2, N):
		dp[i][i // 2] = max(dp[i - 2][i // 2 - 1] + A[i], dp[i - 1][i // 2])
		dp[i][i // 2 + 1] = max(dp[i - 2][i // 2] + A[i], dp[i - 1][i // 2 + 1])
	print(dp[N - 1][N // 2])
main()


def main():
	import sys
	input = sys.stdin.readline
	n = int(input())
	A = list(map(int, input().split()))
	A_ = [0] * n
	for i in range(n):
		if i % 2 == 0:
			A_[i] = A[i]
		else:
			A_[i] == 0
	for i in range(n - 1):
		A_[i + 1] += A_[i]
	dp = [0] * n
	dp[1] = max(A[0], A[1])
	for i in range(2, n):
		if i % 2 == 0:
			dp[i] = max(dp[i - 2] + A[i], dp[i - 1])
		else:
			dp[i] = max(dp[i - 2] + A[i], A_[i - 1])
	print(dp[n - 1])
main()


from sys import stdin
input = stdin.readline
n = int(input())
a = [int(x) for x in input().split()]
dp = [[0] * 3 for x in range(n)]
dp[0][0] = a[0]
dp[1][1] = a[1]
if n > 2:
	dp[2][0] = a[0] + a[2]
	dp[2][2] = a[2]
if n > 3:
	dp[3][1] = max(a[0] + a[3], a[1] + a[3])
for x in range(4, n):
	if x % 2 == 0:
		dp[x][0] = dp[x - 2][0] + a[x]
	dp[x][1] = max(dp[x - 2][1] + a[x], dp[x - 3][0] + a[x])
	dp[x][2] = max(dp[x - 2][2] + a[x], dp[x - 3][1] + a[x], dp[x - 4][0] + a[x])
if n % 2 == 0:
	print(max(dp[-2][0], dp[-1][1]))
else:
	print(max(dp[-3][0], dp[-2][1], dp[-1][2]))


N = int(input())
A = list(map(int, input().split()))
dp = [{} for __ in range(N + 1)]
dp[0][0] = 0
dp[1][0] = 0
dp[1][1] = A[0]
for i in range(2, N + 1):
	for j in range((i - 1) // 2, (i + 1) // 2 + 1):
		app = (dp[i - 2][j - 1] if j - 1 in dp[i - 2] else -float('inf')) + A[i - 1]
		napp = dp[i - 1][j] if j in dp[i - 1] else -float('inf')
		dp[i][j] = max(app, napp)
print(dp[N][N // 2])


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 = 1e+18
	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()


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()))
assert len(a) == n
l = [0] * n
u = [0] * n
l[0] = 0
u[0] = a[0]
u[1] = max(a[:2])
l[1] = u[1]
for i in range(2, n):
	l[i] = max(u[i - 1], l[i - 2] + a[i])
	u[i] = u[i - 2] + a[i]
	if i % 2 != 0:
		u[i] = max(u[i - 1], u[i])
print(l[-1])


import sys
sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline

def solve():
	N = int(rl())
	A = list(map(int, rl().split()))
	dp = [0] * N
	dp[1] = max(A[:2])
	odd = A[0]
	for i in range(2, N):
		if i % 2 == 0:
			odd += A[i]
			dp[i] = max(dp[i - 2] + A[i], dp[i - 1])
		else:
			dp[i] = max(dp[i - 2] + A[i], odd)
	print(dp[-1])
solve()


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)


import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
inf = float('inf')

def main():
	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(ans)

def __starting_point():
	main()
__starting_point()


import sys
n = int(input())
a = list(map(int, input().split()))
if n == 2:
	print(max(a))
	sys.exit()
a0 = [a[0], a[0]]
a1 = [0, a[1]]
a2 = [0, 0, a[2]]
for i in range(2, n):
	if i % 2 == 0:
		a0.append(a0[i - 2] + a[i])
		a1.append(a1[i - 1])
		if i >= 4:
			a2.append(max(a2[i - 2], a1[i - 3], a0[i - 4]) + a[i])
	else:
		a0.append(a0[i - 1])
		a1.append(max(a1[i - 2], a0[i - 3]) + a[i])
		a2.append(a2[i - 1])
if n % 2 == 1:
	print(max(a0[n - 1], a1[n - 1], a2[n - 1]))
else:
	print(max(a0[n - 1], a1[n - 1]))


N = int(input())
A = list(map(int, input().split()))
ans = sum(A[1::2])
dA = []
for (a1, a2) in zip(A, A[1:]):
	dA.append(a1 - a2)
max_cum_l = 0
cum_l = 0
L = [0]
for idx_l in range(0, N - 1, 2):
	cum_l += dA[idx_l]
	max_cum_l = max(max_cum_l, cum_l)
	L.append(max_cum_l)
max_cum_r = 0
cum_r = 0
R = [0]
for idx_r in range(N - 2, -1, -2):
	cum_r -= dA[idx_r]
	max_cum_r = max(max_cum_r, cum_r)
	R.append(max_cum_r)
R.reverse()
if N % 2:
	ma = -(1 << 60)
	for (l, r) in zip(L, R):
		if ma < l + r:
			ma = l + r
	print(ans + ma)
else:
	print(max(L) + ans)


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


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])


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())
l = list(map(int, input().split()))
INF = 10 ** 17
start = []
start.append((0, l[0]))
start.append((0, max(l[0], l[1])))
for i in range(2, N):
	if i % 2 == 0:
		left = [start[-1][1], start[-2][0] + l[i]]
		right = [start[-2][1] + l[i]]
	else:
		left = [start[-1][0], start[-2][0] + l[i]]
		right = [start[-1][1], start[-2][1] + l[i]]
	start.append((max(left), max(right)))
if N % 2:
	print(start[-1][0])
else:
	print(start[-1][1])


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)


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))
	A = [int(next(tokens)) for _ in range(N)]
	solve(N, A)

def __starting_point():
	main()
__starting_point()


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	from collections import defaultdict
	dp = defaultdict(lambda : -float('inf'))
	dp[0, 0, 0] = 0
	for i in range(1, n + 1):
		max_j = i // 2 if i % 2 == 0 else i // 2 + 1
		min_j = n // 2 - (n - i) // 2 if (n - i) % 2 == 0 else n // 2 - ((n - i) // 2 + 1)
		for j in range(min_j, max_j + 1):
			dp[i, j, 0] = max(dp[i - 1, j, 0], dp[i - 1, j, 1])
			dp[i, j, 1] = dp[i - 1, j - 1, 0] + a[i - 1]
	print(max(dp[n, n // 2, 0], dp[n, n // 2, 1]))
solve()


INF = float('inf')
n = int(input())
a = list(map(int, input().split())) + [0] * 5
s = 2 + n % 2
dp = [[-INF] * s for _ in range(n + 5)]
for i in range(s):
	dp[i][i] = a[i]
for i in range(n):
	for j in range(s):
		dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + a[i + 2])
		if j == s - 1:
			break
		dp[i + 3][j + 1] = max(dp[i + 3][j + 1], dp[i][j] + a[i + 3])
print(max([dp[n - i][s - i] for i in range(1, s + 1)]))


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():
	INF = 10 ** 18
	N = int(input())
	A = list(map(int, input().split(' ')))
	K = 1 + N % 2
	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:
				now += A[i]
			dp[i + 1][j] = max(dp[i + 1][j], now)
	print(dp[N][K])

def __starting_point():
	main()
__starting_point()


from collections import defaultdict
INF = -1000000000000001
n = int(input())
l = list(map(int, input().split()))
a = int(n / 2)
dpa = defaultdict(lambda : -INF)
dpa[0, 0] = 0
dpa[1, 0] = 0
dpa[1, 1] = l[0]
j = 1
for i in range(2, n + 1):
	if i == j * 2:
		dpa[i, j] = max(dpa[i - 2, j - 1] + l[i - 1], dpa[i - 1, j])
	else:
		dpa[i, j] = max(dpa[i - 2, j - 1] + l[i - 1], dpa[i - 1, j])
		if i != n:
			j += 1
			dpa[i, j] = dpa[i - 2, j - 1] + l[i - 1]
print(dpa[n, a])


n = int(input())
a = [int(c) for c in input().split()]
m = 0
t0 = [-1] * n
t1 = [-1] * n
t2 = [-1] * n
t0[-1] = a[-1]
t1[-1] = 0
t2[-1] = a[-1]
tmp = 0
for i in range(-1, -n - 1, -2):
	tmp += a[i]
	t2[i] = tmp
tmp = 0
for i in range(-2, -n - 1, -2):
	tmp += a[i]
	t2[i] = tmp
for i in range(-2, -n - 1, -1):
	if i % 2 == 0:
		m = a[i] + t1[i + 1]
		m = max(m, t2[i + 1])
		t0[i] = m
		t1[i] = t0[i + 1]
	else:
		m = a[i] + t1[i + 1]
		m = max(m, t0[i + 1])
		t0[i] = m
		t1[i] = t0[i + 1]
print(t0[0])


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))


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]))


import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)
N = int(input())
A = list(map(int, input().split()))
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
	if index >= N:
		return -INF
	if N - index < 2 * n - 1:
		return -INF
	if n == 0:
		return 0
	elif n == 1:
		return max(A[index:])
	ret = max(A[index] + F(index + 2, n - 1), F(index + 1, n))
	return ret
answer = F(0, N // 2)
print(answer)


import sys
stdin = sys.stdin
ns = lambda : stdin.readline().rstrip()
ni = lambda : int(stdin.readline().rstrip())
nm = lambda : map(int, stdin.readline().split())
nl = lambda : list(map(int, stdin.readline().split()))
n = ni()
a = nl()
dp = [[0] * 3 for _ in range(n + 5)]
t = n % 2
for i in range(n):
	dp[i][0] = dp[i - 2][0] + a[i]
	dp[i][1] = max(dp[i - 2][1], dp[i - 3][0]) + a[i]
	if t:
		dp[i][2] = max(dp[i - 2][2], dp[i - 3][1], dp[i - 4][0]) + a[i]
if t:
	print(max(dp[n - 3][0], dp[n - 2][1], dp[n - 1][2]))
else:
	print(max(dp[n - 2][0], dp[n - 1][1]))


def f_select_half():
	from collections import defaultdict
	N = int(input())
	A = [int(i) for i in input().split()]
	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])
			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())


n = int(input())
a = list(map(int, input().split()))
choice = n // 2
dic1 = {0: 0}
dic2 = {0: 0, 1: a[0]}
for i in range(1, n):
	mini = choice - (n - i + 1) // 2
	new = {}
	for j in range(mini, (i + 2) // 2 + 1):
		if j == 0:
			new[j] = 0
			continue
		if j in dic2:
			new[j] = max(dic2[j], dic1[j - 1] + a[i])
		else:
			new[j] = dic1[j - 1] + a[i]
	dic1 = dic2
	dic2 = new
print(dic2[choice])


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


INF = 10 ** 18

def solve(n, a):
	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))


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()))
a0 = [0] * (n // 2 + 1)
a1 = [0] * (n // 2 + 1)
for i in range(n // 2):
	a0[i + 1] = a0[i] + a[i * 2]
if n % 2 != 0:
	a0.append(a0[-1] + a[-1])
max_even = [0] * (n // 2 + 1)
for i in range(n // 2):
	max_even[i + 1] = max(max_even[i] + a[2 * i + 1], a0[i + 1])
ans = -1000000000.0 * n
if n % 2 == 0:
	ans = max_even[-1]
else:
	for i in range(0, n // 2 + 1):
		ans = max(ans, max_even[i] + a0[-1] - a0[i + 1])
print(ans)


from collections import defaultdict
INF = 10 ** 15
N = int(input())
A = list(map(int, input().split()))
dp_take = defaultdict(lambda : -INF)
dp_not = defaultdict(lambda : -INF)
dp_take[0, 0] = 0
dp_not[0, 0] = 0
for i in range(N):
	for j in range((i + 1) // 2 - 1, (i + 2) // 2 + 1):
		if j > 0:
			dp_take[i + 1, j] = max(dp_take[i + 1, j], dp_not[i, j - 1] + A[i])
		dp_not[i + 1, j] = max(dp_not[i, j], dp_take[i, j])
print(max(dp_take[N, N // 2], dp_not[N, N // 2]))


N = int(input())
A = tuple(map(int, input().split()))
from collections import defaultdict
dp_non = defaultdict(lambda : -2 ** 60)
dp_take = defaultdict(lambda : -2 ** 60)
dp_non[0, 0] = 0
for (i, x) in enumerate(A, 1):
	j = (i - 1) // 2
	for n in (j, j + 1):
		dp_non[i, n] = max(dp_non[i - 1, n], dp_take[i - 1, n])
		dp_take[i, n] = dp_non[i - 1, n - 1] + x
print(max(dp_non[N, N // 2], dp_take[N, N // 2]))


N = int(input())
A = list(map(int, input().split()))
answer = [max(A[0], A[1])]
list_sum = A[::2]
for i in range(1, len(list_sum)):
	list_sum[i] += list_sum[i - 1]
for i in range(2, N):
	if i == 2:
		answer.append(max(A[0], A[1], A[2]))
	elif i % 2 == 0:
		answer.append(max(answer[-1], answer[-2] + A[i]))
	else:
		answer.append(max(answer[-2] + A[i], list_sum[(i - 1) // 2]))
print(answer[-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)


n = int(input())
a = list(map(int, input().split()))
dp0 = 0
dp1 = 0
dp2 = 0
for i in range(1, n + 1):
	ai = a[i - 1]
	if i % 2:
		dp1 = max(dp0, dp1)
		dp0 += ai
	if i % 2 == 0:
		dp2 = max(dp1, dp2)
		dp1 += ai
	if i >= 3 and i % 2:
		dp2 += ai
if n % 2 == 0:
	print(max(dp0, dp1))
else:
	print(max(dp1, dp2))


N = int(input())
A = list(map(int, input().split()))
dp = [[-10 ** 18 for i in range(N // 2 + 1)] for j in range(2)]
dp[0][0] = 0
dp[1][1] = A[0]
dp[1][0] = 0
for i in range(2, N + 1):
	high = min(N // 2, i // 2 + 10)
	low = max(0, i // 2 - 10)
	for j in range(high, low, -1):
		dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[i % 2][j - 1] + A[i - 1])
print(dp[N % 2][N // 2])


N = int(input())
A = [0, 0] + list(map(int, input().split())) + [0, 0]
skip = N - 2 * (N // 2) + 1
dp = [[-10 ** 18] * (skip + 1) for _ in range(N + 4)]
for i in range(2):
	for j in range(skip + 1):
		dp[i][j] = 0
for i in range(2, N + 4):
	for j in range(skip + 1):
		dp[i][j] = max(dp[i][j], dp[i - 2][j] + A[i])
		if i >= 3 and j + 1 <= skip:
			dp[i][j + 1] = max(dp[i][j + 1], dp[i - 3][j] + A[i])
		if i >= 4 and j + 2 <= skip:
			dp[i][j + 2] = max(dp[i][j + 2], dp[i - 4][j] + A[i])
print(dp[N + 3][skip])


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()))
kin = [0] * N
gin = [0] * N
if N <= 3:
	print(max(A))
else:
	kin[0] = A[0]
	kin[1] = A[1]
	kin[2] = kin[0] + A[2]
	gin[2] = A[2]
	for i in range(3, N):
		if i % 2 == 1:
			kin[i] = max(kin[i - 2], kin[i - 3]) + A[i]
		else:
			kin[i] = kin[i - 2] + A[i]
			gin[i] = max(kin[i - 3], gin[i - 2]) + A[i]
	if N % 2 == 0:
		print(max(kin[N - 1], kin[N - 2]))
	else:
		print(max(gin[N - 1], kin[N - 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])


n = int(input())
l = list(map(int, input().split()))
dp = [[-float('INF')] * 3 for i in range(n + 1)]
dp[0][0] = 0
dp[1][-1] = 0
dp[1][1] = l[0]
for i in range(1, n):
	dp[i + 1][-1] = max(dp[i][0], dp[i - 1][-1] + l[i])
	dp[i + 1][0] = max(dp[i][1], dp[i - 1][0] + l[i])
	dp[i + 1][1] = dp[i - 1][1] + l[i]
print(max(dp[-1][0], dp[-1][-1]))


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


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())
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]))


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])


import math
import sys
sys.setrecursionlimit(1000000)
N = int(input())
A = [int(i) for i in input().split()]
memo = {}

def sub_max(n, m):
	if (n, m) in memo:
		return memo[n, m]
	if m == 1 and n >= 1:
		memo[n, m] = max(A[-n:])
		return memo[n, m]
	if m > math.ceil(n / 2):
		memo[n, m] = -float('inf')
		return -float('inf')
	res = -float('inf')
	for i in range(3):
		res = max(res, A[-n + i] + sub_max(n - i - 2, m - 1))
	memo[n, m] = res
	return res
print(sub_max(N, N // 2))


n = int(input())
a = list(map(int, input().split()))
if n % 2 == 0:
	a.append(-float('inf'))
	n += 1
if n == 3:
	print(max(a))
	exit()
p0 = a[0]
z0 = -float('inf')
z1 = a[1]
y0 = a[0] + a[2]
y1 = -float('inf')
y2 = a[2]
x0 = -float('inf')
x1 = max(p0, z1) + a[3]
x2 = -float('inf')
for i in range(4, n - 1):
	w0 = y0 + a[i]
	w1 = max(y1, z0) + a[i]
	w2 = max(y2, z1, p0) + a[i]
	p0 = z0
	z0 = y0
	z1 = y1
	y0 = x0
	y1 = x1
	y2 = x2
	x0 = w0
	x1 = w1
	x2 = w2
w0 = y0 + a[n - 1]
w1 = max(y1, z0) + a[n - 1]
w2 = max(y2, z1, p0) + a[n - 1]
print(max(y0, x1, w2))


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())


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))))

def main():

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

def __starting_point():
	main()
__starting_point()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict
INF = 10 ** 18
(N, *A) = map(int, read().split())
dp_not = defaultdict(lambda : -INF)
dp_take = defaultdict(lambda : -INF)
dp_not[0, 0] = 0
for (i, x) in enumerate(A, 1):
	j = (i - 1) // 2
	for n in (j, j + 1):
		dp_not[i, n] = max(dp_not[i - 1, n], dp_take[i - 1, n])
		dp_take[i, n] = dp_not[i - 1, n - 1] + x
print(max(dp_not[N, N // 2], dp_take[N, N // 2]))


import copy
n = int(input())
a = list(map(int, input().split()))
k = 1 + n % 2
INF = 10 ** 18
dp = [[-INF] * 4 for i in range(n + 5)]
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 = copy.deepcopy(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])