[Baltic2015]Hacker

时间限制:10s      空间限制:256MB

题目描述

 有n个数围成一个圈,第i个数是a[i]。

Alice和Bob互相挑选数字,一个数被其中一方选中后,另一方不能选。Alice先挑,Bob后挑。
第一轮过后,接下来每一轮每个人选的数字都得和自己上一个选的相邻。
当所有数字都被选中后,游戏结束。
Alice想让自己选中的数字之和最大,Bob想让Alice选中的数字之和越小越好。
问Alice在最优策略下,能拿到的数字之和的最大值。


输入格式

第一行,一个数n;

第二行,n个数,a[1],a[2],...,a[n]。


输出格式

一个数表示答案


样例输入

4
7 6 8 4

样例输出

13

提示

 n <= 500000, 1 <= a[i] <= 2000

求译文!请发至lydsy2012@163.com


题目来源

没有写明来源