rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans=-1e9,fl,cnt,st;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
struct node{
	int val,cnt,cost;
}zxw[10000010];
bool cmp(node zxw1,node zxw2){
	if(zxw1.cost==zxw2.cost){
		if(zxw1.val==zxw2.val){
			return zxw1.cnt<zxw2.cnt;
		}
		return zxw1.val>zxw2.val;
	}
	return zxw1.cost>zxw2.cost;
}
signed main(){
	ios::sync_with_stdio(0);
	st=clock();
	n=read();
	for(register int i=1;i<=n;++i){
		zxw[i].val=read();
		zxw[i].cnt=i;
		zxw[i].cost=(long long)zxw[i].cnt*zxw[i].val;
		ans=max(ans,i*zxw[i].val);
		if(zxw[i].val!=cnt&&i>1){
			fl=1;
		}
		cnt=zxw[i].val;
	}
	if(fl==0){
		cout<<(long long)((long long)zxw[1].val*(long long)(n*2-1));
		return 0;
	}
	if(n>1e6){
		sort(zxw+n-8000,zxw+n+1,cmp);
		for(int i=n-8000;i<=n;i++){
			for(int j=n-8000;j<=n;j++){
				if(i==j){
					continue;
				}
				ans=max(ans,min(zxw[i].val,zxw[j].val)*(zxw[i].cnt+zxw[j].cnt));
			}
		}
		cout<<ans;
		return 0;
	}
	sort(zxw+1,zxw+min(n,1000000ll)+1,cmp);
	for(int i=1;i<=min(1000ll,n);i++){
		for(int j=1;j<=min(1000ll,n);j++){
			if(i==j){
				continue;
			}
			ans=max(ans,min(zxw[i].val,zxw[j].val)*(zxw[i].cnt+zxw[j].cnt));
		}
	}
	cout<<ans;
}

数据范围分治(