题目描述

给定一个长度为 $N$ 的整数序列 $A_1,…, A_N$。

我们将从这个序列中选择恰好学$⌊\frac N 2⌋$ 个元素，使得任意两个相邻的元素都没有被选中。

求被选中的元素的最大可能和。 这里$⌊x⌋$ 表示不超过 $x$ 的最大整数。

输入

第一行输入一个整数$N$

接下来一共输入$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$