#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const int INF = int (1e9) + int (1e5);
const ll INFL = ll(2e18) + ll(1e10);
const ui MOD = 1E9 + 7;
const double EPS = 1e-9;
#define FOR(i,n) for (int i=0;i<(n);++i)
#define ROF(i,x) for(int i = (x) ; i >= 0 ; --i)
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define ODD(x) (((x)&1)==0?(0):(1))
#define sign(x) ((x > 0) - (x < 0))
std::mt19937_64  generator(std::chrono::system_clock::now().time_since_epoch().count());

inline ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a, ll b) { return a ? gcd(b%a, a): b; }
ll lcm(ll a, ll b) { return a / gcd(a,b) * b; }


void READ(bool _local){
    ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef _DEBUG
    if (_local)
        freopen ("in.txt", "r", stdin);
#endif
}


typedef struct node* pnode;
typedef int T;

struct item {
    int key, prior;
    item * l, * r;
    item() { }
    item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};
typedef item * pitem;

void split (pitem t, int key, pitem & l, pitem & r) {
    if (!t)
        l = r = NULL;
    else if (key < t->key)
        split (t->l, key, l, t->l),  r = t;
    else
        split (t->r, key, t->r, r),  l = t;
}

void insert (pitem & t, pitem it) {
    if (!t)
        t = it;
    else if (it->prior > t->prior)
        split (t, it->key, it->l, it->r),  t = it;
    else
        insert (it->key < t->key ? t->l : t->r, it);
}

void search(pitem t, int v,ii &ret){
    if (!t) return;
    if (t->key>v){
        if (ret.first!=INF) {
            if (ret.second==INF || ret.second<t->prior) ret.second=t->prior;
            return;
        }
        ret.first=t->prior;
        if (t->key!=v+1) search(t->l,v,ret);
        search(t->r,v,ret);
    }else{
        search(t->r,v,ret);
    }
}

void merge (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
}

void erase (pitem & t, int key) {
    if (t->key == key)
        merge (t, t->l, t->r);
    else
        erase (key < t->key ? t->l : t->r, key);
}

pitem unite (pitem l, pitem r) {
    if (!l || !r)  return l ? l : r;
    if (l->prior < r->prior)  swap (l, r);
    pitem lt, rt;
    split (r, l->key, lt, rt);
    l->l = unite (l->l, lt);
    l->r = unite (l->r, rt);
    return l;
}

int main() {
    READ(0);
    int n;cin>>n;
    vi p(n);
    pitem t=NULL;
    pitem t2=NULL;
    FOR(i,n){
        cin>>p[i];
    }
    insert(t,new item(p[0],0));
    vii nextl(n,ii(INF,INF)),nextr(n,ii(INF,INF));
    for(int i=1;i<n;++i){
        search(t,p[i],nextl[i]);
        insert(t,new item(p[i],i));
    }
    insert(t2,new item(p[n-1],-n+1));
    for(int i=n-2;i>=0;--i){
        search(t2,p[i],nextr[i]);
        insert(t2,new item(p[i],-i));
    }
    ll ans=0;
    FOR(i,n){
        if (p[i]==n) continue;
        ll cuantos=0;
        if (nextl[i].first!=INF){
            int l1=(nextl[i].second==INF?0:nextl[i].second+1);
            int l2=nextl[i].first;
            int r1=i;
            int r2=(nextr[i].first==INF ? n-1:-nextr[i].first-1);
            cuantos += max(0LL,(ll)(r2-r1+1)*(l2-l1+1));
            if (nextr[i].first!=INF) {
                l1 = nextl[i].first + 1;
                l2 = i;
                r1=-nextr[i].first;
                r2 = (nextr[i].second==INF ? n-1:-nextr[i].second-1);
                cuantos += max(0LL,(ll)(l2-l1+1)*(r2-r1+1));
            }
        }else{
            int l1=0,l2=i;
            int r1=-nextr[i].first;
            int r2=(nextr[i].second==INF?n-1:-nextr[i].second-1);
            cuantos += max(0LL,(ll)(l2-l1+1)*(r2-r1+1));
        }
        ans += cuantos*p[i];
    }
    cout << ans;

    return 0;
}



Measured memory_bytes: 8448