记录编号	602755	评测结果	AAAAA
题目名称	2698.环路运输	最终得分	100
用户昵称	rb_tree	是否通过	通过
代码语言	C++	运行时间	0.195 s
提交时间	2025-07-05 16:35:16	内存使用	7.06 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
	int x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*w;
}
void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>=10) write(x/10);
	putchar((x%10)^48);
}
int a[2000005],n,ans=-0x7fffffff;
signed main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=a[i+n]=read();
    deque<int> q;
    for(int i=1;i<=n<<1;i++)
    {
        while(!q.empty()&&i-q.front()>n>>1) q.pop_front();
        if(!q.empty()) ans=max(ans,a[i]+a[q.front()]+i-q.front());
        while(!q.empty()&&a[q.back()]-q.back()<a[i]-i) q.pop_back();
        q.push_back(i);
    }
    write(ans);
    return 0;
}