美味

桌上摆着环形的 \(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

看到数据范围，我们考虑用区间dp解决。看到环，想到破环成链。定义\(dp_{l,r}\)为已经吃了\(l\)到\(r\)时DD能吃到的最大值。

我们就可以通过区间大小来判断到谁了啦。如果是偶数就是DD，如果是奇数就到萨摩耶。如果到DD，那就\(dp_{l+1,r}+a_l\)和\(dp_{l,r-1}+a_r\)中去最大值，这样子肯定对于DD来说是最有策略。如果到萨摩耶，那就看如果符合\(a_l\geq a_{r+1}\),那他有可能上次吃掉了\(a_l\)同理，如果符合\(a_r\geq a_{l-1}\),上一次有可能吃掉了\(a_r\)。

#include 
using namespace std;
const long long INF=1e15;
const int N=6005;
int n;
int a[N];
long long rmb[N][N];
long long ans;
long long dfs(int l,int r)
{
	
	if(l>r)
		return 0;
	if(r>2*n)
		return 0;
	if(l==r)
		return a[l];
	if(rmb[l][r]=a[r+1])
			p=max(p,dfs(l+1,r));
		if(a[r]>=a[l-1])
			p=max(p,dfs(l,r-1));
		return rmb[l][r]=p;
	}
	
}
int main()
{
	cin>>n;
	memset(rmb,1,sizeof(rmb));
	for(int i=1;i<=n;i++)
		cin>>a[i];
	a[0]=a[n];
	for(int i=1;i<=n;i++)
		a[i+n]=a[i];
	for(int i=1;i<=n;i++)
		ans=max(ans,dfs(i,i+n-1));
	cout<