Description

在一条环形公路旁均匀地分布着 $N$ 座仓库，编号为 $1..N$，编号为 $i$ 的仓库与编号为 $j$ 的仓库之间的距离定义为 $dist(i,j)=min(|i-j|,N-|i-j|)$，也就是逆时针或顺时针从 $i$ 到 $j$ 中较近的一种。
每座仓库都存有货物，其中编号为 $i$ 的仓库库存量为 $A_i$。
在 $i$ 和 $j$ 两座仓库之间运送货物需要的代价为 $A_i+A_j+dist(i,j)$。
求在哪两座仓库之间运送货物需要的代价最大。

Input

第一行包含一个整数 $N$。
第二行包含 $N$ 个整数 $A_1..A_N$。

Output

输出一个整数，表示最大代价。

Hint

$1≤N≤10^6,$
$1≤A_i≤10^7$

Sample Input

5
1 8 6 2 5

Sample Output

15

Analyse

这一题很明显地出现了环形的情况，我们只要把数组延长一倍就好了——算是基操了吧，至于如何状态转移：

• 假如 $i-j\gt N/2$，那么 $j$ 对 $i$ 来说就没有用了；（后面会有机会使 $(j+N)-i\le N/2$，让 $i$ 更新 $j$，毕竟这是一个环）
• 假如 $A_i\ge A_j+(i-j)\ (1\le j\lt i\le N\cdot 2\ \ and\ \ (i-j)\le N/2)$ ,那么，$j$ 也可以宣告无用了；（还不如让 $i$ 更新后面）

乍一看：不就是个单调队列吗？ 是的没错，$O(N)$ 可以过。

#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+10;
inline int mymax(int a,int b) {return a>b?a:b;}
inline int read()
{
    int x=0;bool f=false;
    char ch=getchar();
    while(ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return f?-x:x;
}
struct node{int p,x;}q[N<<1];
//x为贡献，因为代价为Ai+Aj+(j-i)，所以i实际对答案贡献了Ai-i
int a[N<<1],head,tail;
int main()
{
    int n=read(),ans=0;
    for(int i=1;i<=n;i++) a[i]=a[i+n]=read();
    q[head=tail=1]=(node){1,a[1]-1};
    for(int i=2;i<=n*2;i++)
    {
        while(head<=tail && i-q[head].p>n/2) head++;
        ans=mymax(ans,q[head].x+a[i]+i);
        int now=a[i]-i;
        while(head<=tail && q[tail].x<=now) tail--;
        q[++tail]=(node){i,now};
    }
    printf("%d\n",ans);
    return 0;
}