/*==============================================*\
ID:          shahidul_brur
 
name:     Md. Shahidul Islam
Study:      CSE, BRUR
Address:  Rangpur, Bangladesh
 
 mail: shahidul.cse.brur@gmail.com
 FB  : fb.com/shahidul.brur
 Blog: shahidul-brur.blogspot.com(in Bengali),
       shahidul-brur-en.blogspot.com(in English)
\*===============================================*/
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> // Common file
//#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz size()
#define all(a)  a.begin(), a.end()
#define mem(a, b)     memset(a, b, sizeof(a))
#define f0(i,b) for(int i=0;i<(b);i++)
#define f1(i,b) for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)
#define rep(i,a,b,c) for(int i=(a);i!=(b);i+=(c))
 
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};

const double pi = acos(-1.0);
const double eps = 1e-6;
const int mod = (int)1e9+7;
const int maxn = (int)5e5+5;
const int logn = 20;
int n, a[maxn], L[maxn], R[maxn], t[maxn], arr_siz;
int firstAtLeast(int L, int R, int K){ /// first index in range [L,R] where value>=K
    if (R < L) return -1;
    int node = L+n-1;
    while(t[node] < K){
        while( (node&1) == 1 ){
            node = node>>1;
            if (node <= 1) return -1;
        }
        ++node;
    }
    while(node < n) {
       node <<= 1;
       if (t[node] < K) ++node;
    }
    int index = node-(n-1);
    return (index <= R ? index : -1);
}
int lastAtLeast(int L, int R, int K){ /// last index in range [L,R] where value>=K
    if (R < L) return arr_siz+1;
    int node = R+n-1;
    while(t[node] < K){
        while( (node&1) == 0 ) {
            node = node>>1;
            if (node <= 1) return -1;
        }       
        --node;
    }
    while(node < n) {
       node = (node<<1)|1;
       if (t[node] < K) --node;
    }
    int index = node-(n-1);
    return (index >= L ? index : -1);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //freopen("in.in", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin>>arr_siz;
    n = 1;
    while(n<arr_siz) n<<=1; 
    mem(t,0);
    f1(i,arr_siz) { 
        cin>>a[i];
        t[i+n-1] = a[i];
    }
    for (int i=n-1; i>0; --i)
        t[i] = max(t[2*i],t[2*i+1]);
    a[0] = arr_siz+1;
    stack<int> stk;
    stk.push(0);
    f1(i,arr_siz){
        while(a[stk.top()]<a[i]) stk.pop();
        L[i] = stk.top();
        stk.push(i);
    }
    
    a[arr_siz+1] = arr_siz+1;
    while(stk.size()>0) stk.pop();
    stk.push(arr_siz+1);
    fr(i,arr_siz,1){
        while(a[stk.top()]<a[i]) stk.pop();
        R[i] = stk.top();
        stk.push(i);
    }
    ll tot = 0;
    f1(i,arr_siz)
    {
        //cout << a[i] << " => " << L[i] << " " << R[i] << "\n";
        if(a[i]==arr_siz) continue;
        if(L[i]>=1){
            int lft = L[i]-1;
            if(L[i]>1) lft = lastAtLeast(1,L[i]-1,a[i]+1);
            if(lft==-1) lft = 0;
            //cout << "   " << a[i] << ": L " << lft << " -> " << L[i] << "\n";
            tot+=(L[i]-lft)*1LL*(R[i]-i)*1LL*a[i];
        }
        if(R[i]>arr_siz) continue;
        int rgt = R[i]+1;
        if(R[i]<arr_siz) rgt = firstAtLeast(R[i]+1,arr_siz,a[i]+1);
        if(rgt==-1) rgt = arr_siz+1;
        //cout << "   " << a[i] << ": R " << R[i] << " -> " << rgt << "\n";
        tot+=(rgt-R[i])*1LL*(i-L[i])*1LL*a[i];
    }
    cout << tot;
    return 0;
}


Measured memory_bytes: 6912