#include<bits/stdc++.h>
using namespace std;
namespace my_std{
	#define ll long long
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 8e18
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
#define LC x<<1
#define RC x<<1|1
set<ll> s1,s2;
vector<ll> vec[1000010];
ll n,a[1000010],lsh[1000010],cnt=0,ans=0;
ll L[1000010],R[1000010],siz[1000010],tree[4000040];
il void pushup(ll x){
	tree[x]=min(tree[LC],tree[RC]);
}
void build(ll x,ll l,ll r){
	tree[x]=inf;
	if(l==r) return;
	ll mid=(l+r)>>1;
	build(LC,l,mid);
	build(RC,mid+1,r);
}
void mdf(ll x,ll l,ll r,ll pos,ll v){
	if(l==r){
		tree[x]=v;
		return;
	}
	ll mid=(l+r)>>1;
	if(pos<=mid) mdf(LC,l,mid,pos,v);
	else mdf(RC,mid+1,r,pos,v);
	pushup(x);
}
ll query(ll x,ll l,ll r,ll ql,ll qr){
	if(ql<=l&&r<=qr) return tree[x];
	ll mid=(l+r)>>1,res=inf;
	if(ql<=mid) res=min(res,query(LC,l,mid,ql,qr));
	if(mid<qr) res=min(res,query(RC,mid+1,r,ql,qr));
	return res;
}
int main(){
	n=read();
	fr(i,1,n) lsh[++cnt]=a[i]=read();
	sort(lsh+1,lsh+cnt+1);
	cnt=unique(lsh+1,lsh+cnt+1)-lsh-1;
	fr(i,1,n) a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;
	fr(i,1,n) vec[a[i]].push_back(i);
	fr(i,1,n) s2.insert(i);
	fr(i,1,cnt){
		fr(j,0,(ll)vec[i].size()-1){
			s1.insert(vec[i][j]);
			s2.erase(vec[i][j]);
		}
		ll l=n+1,r=0;
		if(!s2.empty()){
			l=*s2.begin();
			r=*(--s2.end());
		}
		while(!s1.empty()&&(*s1.begin())<=l) s1.erase(*s1.begin());
		while(!s1.empty()&&(*(--s1.end()))>=r) s1.erase(*(--s1.end()));
		if(s1.empty()) continue;
		L[i]=*s1.begin();
		R[i]=*(--s1.end());
		siz[i]=s1.size();
	}
	build(1,1,n);
	pfr(i,cnt,1){
		if(siz[i]){
			ll prel=query(1,1,n,1,L[i]-1),sufl=query(1,1,n,L[i]+1,n),prer=query(1,1,n,1,R[i]-1),sufr=query(1,1,n,R[i]+1,n);
			if(siz[i]==1){
				ans+=(prel+sufl)*(lsh[i+1]-lsh[i]);
				ans+=(lsh[i]+lsh[i+1]-1)*(lsh[i+1]-lsh[i])/2;
			}
			else if((prel+sufl+sufr)<=(prel+prer+sufr)){
				ans+=(prel+sufl+sufr+2*siz[i]-3)*(lsh[i+1]-lsh[i]);
				ans+=(3*siz[i]-3)*(lsh[i]+lsh[i+1]-1)*(lsh[i+1]-lsh[i])/2;
			}
			else{
				ans+=(prel+prer+sufr+2*siz[i]-3)*(lsh[i+1]-lsh[i]);
				ans+=(3*siz[i]-3)*(lsh[i]+lsh[i+1]-1)*(lsh[i+1]-lsh[i])/2;
			}
		}
		fr(j,0,(ll)vec[i].size()-1) mdf(1,1,n,vec[i][j],lsh[i]);
	}
	write(ans);
}