1204 - 3n 块披萨

通过次数

5

提交次数

16

时间限制 : 1 秒
内存限制 : 128 MB

给你一个披萨,它由 3n 块不同大小的部分组成,现在你和你的朋友们需要按照如下规则来分披萨:

你挑选 任意 一块披萨。 Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。 Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。 重复上述过程直到没有披萨剩下。 每一块披萨的大小按顺时针方向由循环数组 slices 表示。

请你返回你可以获得的披萨大小总和的最大值。

输入

输入共2行。

第一行为整数n,表示有多少块披萨。

第二行为n个整数,表示每块披萨的大小。

输出

一个整数,表示你可以获得的披萨大小总和的最大值。

样例

输入

6
8 9 8 6 1 1

输出

16

输入

6
1 2 3 4 5 6

输出

10

提示

1 \leq slices.length \leq 500

slices.length \% 3 == 0

1 \leq slices[i] \leq 1000