选一半

题目描述

给出长度为 $N$ 的整数列 $A_1,...,A_N$。

从中恰好选出 $\left\lfloor \frac{N}{2} \right\rfloor$ 个整数,且任意选出的两个位置不能连续。

求选出的元素之和可能达到的最大值。

其中,$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

• $2 \leq N \leq 2\times 10^5$
• $|A_i|\leq 10^9$
• 输入均为整数