#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
#define MAXN 10010
using namespace std;
 
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if (ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int n;
int h[MAXN],lsh[MAXN];
signed ll[MAXN][MAXN],rr[MAXN][MAXN];
int f[MAXN],g[MAXN];
int aa[MAXN];
 
inline int _max(int x,int y){
	return (x>y)?x:y;
}
 
signed main(){
	n=read();
	for(int i=1;i<=n;i++)
		lsh[i]=h[i]=read();
	sort(lsh+1,lsh+1+n);
	int tot=unique(lsh+1,lsh+1+n)-lsh-1;
	for(int i=1;i<=n;i++)
		h[i]=lower_bound(lsh+1,lsh+1+tot,h[i])-lsh;
	
	int ans=0;
	for(int i=1;i<=n;i++){
		aa[i]=aa[i-1];
		for(int j=1;j<=h[i];j++)
			ll[i][j]=ll[i-1][j]+1,aa[i]=_max(aa[i],lsh[j]*ll[i][j]);
	}
	for(int i=n;i;i--)
		for(int j=1;j<=h[i];j++)
			rr[i][j]=rr[i+1][j]+1,
			ans=_max(ans,aa[i-1]+lsh[j]*rr[i][j]);
			
	for(int i=1;i<=n;i++){
		int l,r;
		for(l=i;l&&h[l]>=h[i];l--);
		l++;
		for(r=i;r<=n&&h[r]>=h[i];r++);
		r--;
		int tmp=1ll*lsh[h[i]]*(r-l+1);
		
		for(int j=1,t=h[i];j<=h[i];j++){
			f[j]=_max(1ll*lsh[j]*ll[r][j],f[j-1]);
			g[j]=_max(1ll*lsh[j]*rr[l][j],g[j-1]);
		
			int lst=lsh[h[i]]-lsh[j];
			ans=_max(ans,tmp+1ll*lsh[j]*(ll[l-1][j]+rr[r+1][j]));
			while(t&&lst<=lsh[t-1])
				t--;
			
			ans=_max(ans,tmp+_max(lsh[j]*ll[l-1][j]+lst*rr[r+1][t],lsh[j]*rr[r+1][j]+lst*ll[l-1][t]));
		}
		for(int j=1,t=h[i];j<=h[i];j++){
			int lst=lsh[h[i]]-lsh[j];
			while(t&&lst<lsh[t])
				t--;
			ans=_max(ans,f[j]+g[t]);
		}
	}
	cout<<ans<<endl;
	return 0;
}