問題文

長さ $N$ の整数列 $A_1,...,A_N$ が与えられます。

この中からちょうど $\\left\\lfloor \\frac{N}{2} \\right\\rfloor$ 個の整数を、どの $2$ 箇所も連続しないように選びます。

選んだ要素の和としてありえる最大値を求めてください。

ここで、$\\lfloor x \\rfloor$ は、$x$ を超えない最大の整数を表します。

制約

• $2 \\leq N \\leq 2\\times 10^5$
• $|A_i|\\leq 10^9$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $...$ $A_N$

出力

選ばれた要素の和としてありえる最大値を出力せよ。

入力例 1

6
1 2 3 4 5 6

出力例 1

12

$2,4,6$ を選ぶと和は $12$ となり、これが最大です。

入力例 2

5
-1000 -100 -10 0 10

出力例 2

0

$\-10,10$ を選ぶと和は $0$ となり、これが最大です。

入力例 3

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

5000000000

オーバーフローに注意してください。

入力例 4

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

出力例 4

295