暂无测试数据。

桌上摆着环形的 $n$ 道菜，每道菜有个美味值，DD 和萨摩耶打算把这 $n$ 道菜吃完，首先 DD 会首先选择一道菜吃掉，两人轮流，接下来每次选择时，DD 和萨摩耶都只能从空的菜盘旁边两个菜中选择。可惜萨摩耶很傻，只会从这两个菜中选择美味值高的吃掉。请问 DD 在最优策略下能吃到的美味值总和是多少。

输入格式

第一行一个整数表示 $n$

接下来一行 $n$ 个整数，$a_i$ 表示第 $i$ 道菜的美味值

输出格式

DD 能吃到美味值总和最大为多少

数据范围

对于 $30\%$ 的数据，$1 \leq n \leq 30$

对于 $60\%$ 的数据，$1 \leq n \leq 500$

对于 $100\%$ 的数据，$1 \leq n \leq 3000, 1 \leq a_i \leq 10^9$

5
1 2 8 9 10

19