题目描述

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

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

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

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

输入格式

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

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

输出格式

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

题目大意

给定长度为$n$的序列$A$，请在这个序列中选择$n/2$(向下取整)个数，并且这些数两两不相邻。

请求出这些数的最大可能和。

6
1 2 3 4 5 6

12

5
-1000 -100 -10 0 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

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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