#include<bits/stdc++.h>

using namespace std;

/*

        Bismillahir Rahmanir Rahim
        Problem :
        Problem Link :
        Topics :
        Solver : Masud Parves
        I Love Code More than Sharks Love Blood <3
*/


#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define SZ(a)           (int)a.size()
#define all(a)  a.begin(), a.end()
#define allr(a)  a.rbegin(), a.rend()


#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)

#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 CIN ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define TEST_CASE(t) for(int zz=1 ; zz<=t ; zz++)
#define PRINT_CASE printf("Case %d: ",zz)
#define Debug(x)            cout<<#x " = "<<(x)<<endl
#define NOT_VISITED 0
#define IS_VISITED 1
#define WHITE 0
#define GRAY 1
#define BLACK 2



int fx[4]= {1,-1,0,0};
int fy[4]= {0,0,1,-1};

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N  (1<<pos);}
//int Reset(int N,int pos){return N= N & ~(1<<pos);}
//bool Check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/


const double PI = acos(-1.0);
const double EPS = 1e-6;
const int MOD = (int)1e9+7;
const int maxn = (int)5e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
typedef pair<int, ll> pill;

int a[maxn], Tree[maxn], L[maxn],R[maxn];
int n,arr_siz;

int ansLeft(int L, int R, int K){
    if(R<L) return arr_siz+1;

    int node = R+n-1;

    while(Tree[node]<K){
        while((node&1)==0){
                node>>=1;
            if(node<=1) return -1;
        }
        node--;
    }

    while(node<n){
        node = (node<<1)|1;
        if(Tree[node]<K) node--;
    }

    int index = node - (n-1);

    return (index>=L ?index : -1);
}

int ansRight(int L, int R, int K){
    if(R<L) return -1;

    int node = L+n-1;

    while(Tree[node]<K){
        while((node&1)==1){
                node>>=1;
            if(node<=1) return -1;
        }
        node++;
    }

    while(node<n){
        node = (node<<1);
        if(Tree[node]<K) node++;
    }

    int index = node - (n-1);

    return (index<=R ? index : -1);
}



int main() {
    CIN
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

  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];
        Tree[i+n-1] = a[i];
    }
    for (int i=n-1; i>0; --i)
        Tree[i] = max(Tree[2*i],Tree[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);
    for(int i=arr_siz ; i>0 ; i--){
        while(a[stk.top()]<a[i]) stk.pop();
        R[i] = stk.top();
        stk.push(i);
    }
    ll ans = 0LL;

    f1(i,arr_siz){

        if(a[i]==arr_siz) continue;

        if(L[i]>=1){
            int left = L[i]-1;
            if(L[i]>1) left = ansLeft(1, L[i]-1, a[i]+1);
            if(left==-1) left=0;
            ans +=(L[i]-left)*1LL*(R[i]-i)*1LL*a[i];
        }

        if(R[i]>arr_siz) continue;
        int right = R[i]+1;
        if(R[i]<arr_siz) right = ansRight(R[i]+1,arr_siz,a[i]+1);
        if(right==-1) right = arr_siz+1;
        ans+=(right-R[i])*1LL*(i-L[i])*1LL*a[i];

    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 5376