配点 : $600$ 点

問題文

長さ $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$

出力

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

6
1 2 3 4 5 6

12

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

5
-1000 -100 -10 0 10

0

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

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

5000000000

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

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

295