#include<bits/stdc++.h>				//Written by ThiDaiLoc
using namespace std;				//Team Three Wolves
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> triple;

#define fu(i,a,b)   for(ll i=a;i<=b;i++)
#define f1(i,n)     for(ll i=1;i<=n;i++)
#define fs(i,s)     for(ll i=0;i+1<=s.length();i++)
#define fd(i,b,a)   for(ll i=b;i>=a;i--)
#define fuv(i,a)    for(ll i=0;i<a.size();i++)
#define fdv(i,a)    for(ll i=(ll)a.size()-1;i>=0;i--)
#define ms(a,x)     memset(a, x, sizeof a)
#define prec(n)     fixed<<setprecision(n)
#define uni(a)      (a).erase(unique(all(a)), (a).end())
#define pb(i)       push_back(i)
#define popb()      pop_back()
#define sc(a)       cin>>a
#define sc2(a,b)    cin>>a>>b
#define pr(a)       cout<<a<<endl
#define pr2(a,b)    cout<<a<<" "<<b<<endl
#define rpr(a)      return cout<<a<<endl,0
#define prY         cout<<"YES"<<endl
#define prN         cout<<"NO"<<endl
#define bit(n,i)    (((n)>>(i))&1)
#define lowb(a,n,x) lower_bound(a,a+n,x) -a
#define upb2(a,x,cmp)   upper_bound(all(a),x,cmp) -a.begin()
#define all(x)      (x).begin(), (x).end()
#define sz(a)       (ll)a.size()
#define le(s)       (ll)s.length()		
#define ast(x,a,b)  assert(x>=a and x<=b)				
#define re          return 	
#define	mp(a,b)     make_pair(a,b)
#define se          second
#define fi          first 
#define debug(x)    cerr << #x << " = " << x << endl
#define INPUT       freopen("locin.txt", "r", stdin)
#define OUTPUT      freopen("locout.txt", "w", stdout)
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline ll mnz(ll& a,ll b){return a=(a>b?b:a);}
inline ll mxz(ll& a,ll b){return a=(a<b?b:a);}
inline string toString(ll n) {stringstream ss; ss << n;return ss.str();}
double const eps = 1e-6;
ll const Base=1e9+7,oo=1e17,MAXN=1e6;


ll A[MAXN+5],AL[MAXN+5],AR[MAXN+5];
ll AL2[MAXN+5],AR2[MAXN+5];
vi saveL[MAXN+5],saveR[MAXN+5];
bool cmp(ll a,ll b){
	re A[a]>A[b];
}
ll Solves(){
	
	ll n,m,k,cnt=0,ans=0,x,y,q,c,sum=0,v,t;
	// PROCESS IN HERE
	sc(n);
	f1(i,n)sc(A[i]);
	A[0]=A[n+1]=oo;
	vi vec; vec.pb(0);
	f1(i,n){
		ll p=upb2(vec,i,cmp);
		AL[i]=vec[p-1]+1;
		saveL[vec[p-1]].pb(i);
		//AL2[i]=(p-2>=0?vec[p-2]+1:1);
		while(A[i]>A[vec.back()])vec.pop_back();
		vec.pb(i);
	}
	vec.clear();
	fu(i,0,n){
		while(sz(saveL[i])){
			if(i==0){
				AL2[saveL[i].back()]=1;
			}
			else{
				ll p=upb2(vec,saveL[i].back(),cmp);
//				if(i==3){
//					fuv(j,vec)debug(vec[j]);
//					debug(p);
//				}
				AL2[saveL[i].back()]=(p-1>=0?vec[p-1]+1:1);
			}
			saveL[i].pop_back();
		}
		while(sz(vec) and A[i]>A[vec.back()])vec.pop_back();
		vec.pb(i);
	}
	debug("b");
	vec.clear(); vec.pb(n+1);
	fd(i,n,1){
		ll p=upb2(vec,i,cmp);
		AR[i]=vec[p-1]-1;
		saveR[vec[p-1]].pb(i);
//		AR2[i]=(p+2<sz(vec)?vec[p+2]-1:n);
//		if(AL[i]!=i)ans+=(AR2[i]-AR[i]+1)*(i-AL[i]+1)*A[i];
//		if(AR[i]!=i)ans+=(AL[i]-AL2[i]+1)*(AR[i]-i+1)*A[i];
//		debug(AL[i]); debug(AR[i]);
//		debug(AL2[i]); debug(AR2[i]);
		while(A[i]>A[vec.back()])vec.pop_back();
		vec.pb(i);
	}
	
	vec.clear();
	fd(i,n+1,1){
		while(sz(saveR[i])){
			if(i==n+1){
				AR2[saveR[i].back()]=n;
			}
			else{
				ll p=upb2(vec,saveR[i].back(),cmp);	
//				if(saveR[i].back()==1){
//						debug(p);fuv(j,vec)debug(vec[j]); debug(saveR[i].back()); debug((p-1<sz(vec)?vec[p-1]-1:n));
//				}
			
				AR2[saveR[i].back()]=(p-1<sz(vec)?vec[p-1]-1:n);
			}
			saveR[i].pop_back();
		}
		while(sz(vec) and A[i]>A[vec.back()])vec.pop_back();
		vec.pb(i);
	}
	//debug("a");
	fu(i,1,n){
		ans+=(AR2[i]-AR[i])*(i-AL[i]+1)*A[i];
		ans+=(AL[i]-AL2[i])*(AR[i]-i+1)*A[i];
		
//		debug(AL[i]); debug(AR[i]);
//		debug(AL2[i]); debug(AR2[i]);
//		debug((AR2[i]-AR[i])*(i-AL[i]+1)); debug((AL[i]-AL2[i])*(AR[i]-i+1));
	}
	
	pr(ans);

	re 0;
	// Hack it if you can :)
}

int main(){
	//INPUT;
	if(fopen("locin.txt", "r"))INPUT;
	ll JUDGE_ONLINE = 1;
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll test=1;
//	sc(test);
	fu(T,1,test){
//		cout<<"Case #"<<T<<": ";
		Solves();
	}
	if (!JUDGE_ONLINE) cout << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";  
		
}

Measured memory_bytes: 64372