問題文
高桥君和青木君长 N 序列 使用 S 玩游戏。
比赛轮到高桥和青木了。 由 1 次组成。
游戏玩法如下。
- 首先,高桥君出了序列的元素 圈 1 。
- 接下来,青木先生选择了高桥先生没有圈出的序列元素。 1 。
- 高桥君和青木君标记了圆圈。 2 对于每个元素,其 2 删除除一个元素之外的所有元素以及它们之间的所有元素。剩余的数列 将其设置为 T 。
- 数列 T 的序列 T 左边奇数元素的总和是高桥的分数,偶数元素的总和是青木的分数。
在可以圈出的元素中,青木会圈出他可以获得最多分数的元素。如果有多个这样的元素,请圈出其中最左边的元素。
高桥君知道如何标记青木君的圆圈。求高桥可以获得的最大可能分数。
入力
输入是按以下格式从标准输入给出的。
N a_1 a_2 ... a_N
- 1 行包含一个整数 N (2≦N≦50) 。 表示N 是一个数字序列 它是 S 中的元素数量。
- 2 行中,N 整数 给出了 a_1, a_2, ... , a_N (-50≦a_i≦50, 1≦i≦N) 。整数 从 a_i 是一个数字序列 它是 S 左侧开始 表示第 i 个元素。
出力
高桥可以获得的最高分数是 1 行输出。
还在输出末尾包含换行符。
入力例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