#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3") 
#pragma GCC optimization ("unroll-loops")
 
// #include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
// const ll RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// gp_hash_table<int, int> table;
 
#define ll  long long
#define vii vector< ll >
#define pb push_back
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define all(x) x.begin(),x.end()
#define S second
#define F first
#define ins insert
#define ld long double
#define lp(l,r) for(i=l;i<=r;++i)
 
#define lpj(l,r) for(j=l;j<=r;++j)
#define lpr(l,r) for(i=r;i>=l;--i)
#define lprj(l,r) for(j=r;j>=l;--j)
 
#define swap(a,b){ auto _t=a;a=b,b=_t;}
#define flush() cout.flush()
#define popcount __builtin_popcount
#define die() return 0;
#define sz() size() 


 
 
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
#define MD          1000000007
#define M           100011
#define N           20
#define fftmod      998244353
#define EPS         (double)1e-10
 
long long  md=MD;
ll inf=1e18;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
 
 
inline ll exp(ll a,ll b){if(a==0&&b==0)return 1ll;if(a==0)return 0ll;ll r=1LL;while(b>0){if(b&1){r=(r%md)*(a%md);r=(r+md)%md;}b/=2;a=(a%md)*(a%md);a=(a+md)%md;}return (r+md)%md;}
ll gcd(ll a,ll b){if(b==0)return a;if(a==0)return b;return gcd(b,a%b);}
inline ll poww(ll a,ll b){ll r=1LL;while(b>0){if(b&1)r=r*a;b/=2;a=a*a;}return (ll)r;}
 
using cd=complex<double>;
const double PI=acos(-1);
 
inline ll rand(ll l,ll r){
    return l+rng()%(r-l+1);
}

ll a[M],f[M],b[M];
ll pos[M];
ll dp[M][N+1];
ll logg[M+1];

ll ma(ll l,ll r){
	if(l>r)return 1e10;
	if(l<0)return 1e10;
	ll j=logg[r-l+1];
	return max(dp[l][j],dp[r-(1<<j)+1][j]);
}
int main(){

 
     
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
   // ifstream fin("input.txt");ofstream fout("outut.txt");
    ll t,i,j,m,n,s,z,k,p;string s1,s2;ll q;ll x,y;
    cin>>n;
    lp(0,n-1)cin>>a[i],pos[a[i]]=i;
    for(i=0;i<n;++i)dp[i][0]=a[i];
    for(j=1;j<=N;++j){
    	for(i=0;i+(1<<j)<=n;++i){
    		dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
    	}
    }logg[1]=0;
    for(i=2;i<=n;++i)logg[i]=logg[i/2]+1;
    for(i=0;i<n;++i){
    	x=-1;p=n;
    	for(;p>=1;p/=2){
    		while(x+p<i&&ma(x+p,i)>a[i])x+=p;
    	}
    	x++;
    	b[i]=x;
    	x=i;p=n;
    	for(;p>=1;p/=2){
    		while(x+p<n&&ma(i,x+p)==a[i])x+=p;
    	}
    	f[i]=x;
    }
    // for(i=0;i<n;++i)trace(a[i],b[i],f[i]);
    // for(i=0;i<n;++i){
    // 	for(j=i;j<n;++j){
    // 		p=ma(i,j);
    // 		trace(p,i,j);
    // 	}
    // }
    ll ans=0;
    for(i=0;i<n;++i){
    	if(a[i]==n)continue;
    	ll nxt=i;
    	ll l=b[nxt]-1,r=f[nxt]+1;
    	x=r,p=n;
    	for(;p>=1;p/=2){
    		while(x+p<n&&max(ma(r+1,x+p),a[i])==a[i])x+=p;
    	}
    	ll r2=x;
    	x=-1,p=n;
    	for(;p>=1;p/=2){
    		while(x+p<l&&max(ma(x+p,l-1),a[i])>a[i])x+=p;
    	}
    	x++;
    	ll l2=x;
    	// trace(i,a[i],l2,l,r,r2);
    	if(r<n)
	    	ans=ans+a[i]*max(0ll,(r2-r+1))*(i-b[i]+1);
    	// trace(ans);
    	if(l>=0)
    		ans=ans+a[i]*max(0ll,(l-l2+1))*(f[i]-i+1);
    	// trace(ans);




    }cout<<ans<<"\n";











}



Measured memory_bytes: 20608