问题描述

高桥君和青木君进行了一个游戏，使用了长度为$N$的数列$S$。

游戏由高桥君和青木君轮流进行一次。

游戏按以下方式进行：

• 首先，高桥君在数列的元素中选择一个加圈。
• 然后，青木君在高桥君没有加圈的元素中选择一个加圈。
• 对于高桥和青木选择的两个加圈的元素，保留这两个元素及它们之间的所有元素，并删除其他元素。将剩下的数列记为$T$。
• 在数列$T$中，左侧奇数位置的元素的总和为高桥的得分，偶数位置的元素的总和为青木的得分。

青木君会选择可以使他得分最高的元素加圈。如果有多个这样的元素，则选择最左边的元素加圈。

高桥君知道青木君加圈的方法。请计算高桥君可以获得的最大得分。

输入

输入从标准输入给出，具体格式如下：

$N$

$a_1$ $a_2$ ... $a_N$

• 第一行包含一个整数$N(2≦N≦50)$，表示数列$S$的元素个数。
• 第二行包含$N$个整数$a_1$，$a_2$，...，$a_N(-50≦a_i≦50, 1≦i≦N)$，表示数列$S$从左到右的第$i$个元素。

输出

输出高桥君可以获得的最大得分。

在输出的末尾要加上换行符。

示例输入1

6
1 -3 3 9 1 6

示例输出1

6

高桥君选择第2个元素是最佳的。在这种情况下，青木君将选择第5个元素，剩余的数列$T$按顺序为-3, 3, 9, 1。高桥君可以得到6分，青木君可以得到4分。

示例输入2

3
5 5 5

示例输出2

10

不管青木君选择哪个元素，他都可以得到5分，但是如果存在多个选择使得获得的分数最大，那么他会选择最左边的元素。因此，高桥君的得分可能是10分。

示例输入3

8
-1 10 -1 2 -1 10 -1 0

示例输出3

-1