桌上摆着环形的 n 道菜，每道菜有个美味值，小王和小何耶打算把这 n 道菜吃完，首先小王会首先选择一道菜吃掉，两人轮流，接下来每次选择时，小王 和小何都只能从空的菜盘旁边两个菜中选择。可惜小何很傻，只会从这两个菜中选择美味值高的吃掉。请问 小王 在最优策略下能吃到的美味值总和是多少。
桌上摆着环形的 n 道菜，每道菜有个美味值，小王和小何耶打算把这 n 道菜吃完，首先小王会首先选择一道菜吃掉，两人轮流，接下来每次选择时，小王 和小何都只能从空的菜盘旁边两个菜中选择。可惜小何很傻，只会从这两个菜中选择美味值高的吃掉。请问 小王 在最优策略下能吃到的美味值总和是多少。
输入文件为table.in
第一行一个整数表示 n
接下来一行 n 个整数， ai 表示第 i 道菜的美味值
输出文件为table.out
小王 能吃到美味值总和最大为多少
5 1 2 8 9 10
19
对于 30% 的数据， 1≤n≤30
对于 60% 的数据， 1≤n≤500
对于 100% 的数据， 1≤n≤3000,1≤ai≤109
********普及模拟题2019-1-D******