前言
不知道为什么题解里的李超线段树都要分两种情况讨论，我觉得的大可不必，其实一遍就好了。
分析
设 \(ans_i\) 为 \(i\) 移动到 其他位置时获得的最大取值，\(sum_i\) 为 \(a_i\) 的前缀和。
对于 $ i < j $ ， \(ans_i=\max \{(j-i)\times a_i-(sum_j-sum_i)\}\) 。
对于 \(i > j\)，\(ans_i=\max \{ sum_i-sum_j+[(i-(j+1))]\times a_i\}\) 。
将两式化简会发现它们都是 \(ans_i=\max \{sum_i-sum_j+(j-i)\times a_i\}\) 。
发现好像没有单调性，并且二分的斜率优化我也不会，就去考虑李超线段树。
将与 \(j\) 相关的式子提出为 \(a_i\times j-sum_j\)，令 \(k=j\)，\(b=-sum_j\)，就可以开始打李超线段树了。
这里大多题解都用了两次 for 循环，正着反着都做了一遍，其实可以将线段先全部插入，再查询，就可以枚举一次了，详见代码，好像还是两次 for 循环。
\(code\)
#include<bits/stdc++.h>
#define N 200005
#define T 2000005
#define int long long
#define ls u<<1
#define rs u<<1|1
#define INF 1e13
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,ans1,ans2;
int tree[T<<2];
int a[N],sum[N],k[N],b[N];
int calc(int x,int id){return x*k[id]+b[id];}
int Query(int u,int l,int r,int x){
if(l==r) return calc(x,tree[u]);
int mid=(l+r)>>1,res=calc(x,tree[u]);
if(x<=mid) res=max(res,Query(ls,l,mid,x));
else res=max(res,Query(rs,mid+1,r,x));
return res;
}
void UpDate(int u,int l,int r,int id){
if(!tree[u]) return void(tree[u]=id);
if(calc(l,id)>calc(l,tree[u])&&calc(r,id)>calc(r,tree[u])) return void(tree[u]=id);
else if(calc(l,id)<=calc(l,tree[u])&&calc(r,id)<=calc(r,tree[u])) return ;
int mid=(l+r)>>1;
if(k[id]>k[tree[u]]){
if(calc(mid,id)>calc(mid,tree[u])) UpDate(ls,l,mid,tree[u]),tree[u]=id;
else UpDate(rs,mid+1,r,id);
}else{
if(calc(mid,id)>calc(mid,tree[u])) UpDate(rs,mid+1,r,tree[u]),tree[u]=id;
else UpDate(ls,l,mid,id);
}
}
signed main(){
n=read();
for(int i=1;i<=n;++i) a[i]=read(),sum[i]=sum[i-1]+a[i],ans2+=i*a[i];
for(int i=1;i<=n;++i){
k[i]=i,b[i]=-sum[i];
UpDate(1,-1e6,1e6,i);
}
for(int i=1;i<=n;++i){
int x=Query(1,-1e6,1e6,a[i]);
ans1=max(ans1,x-i*a[i]+sum[i]);
}
printf("%lld\n",ans2+ans1);
return 0;
}