题目描述

有 n 个数从左往右排成一行，第 i 个数是 a[i] 。

你要从这 n 个数里面选出 n/2 个数，使得这 n/2 个的总和最大，前提是你不能选择位置相邻的数。

注意:这里的 n/2 是整除，向下取整，不是实数的除法。

输入格式

第一行，一个整数 n ( 2 <= n <= 200000 )。

第二行，n 个整数，第 i 个整数是 a[i] ( -1000000000 <= a[i] <= 1000000000 )

提示：有 30% 的数据 n<30 。

输出格式

一个整数。

样例

5
-1000 -100 -10 0 10

0

6
1 2 3 4 5 6

12