#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#ifdef DEBUG
template<class T>
ostream& operator << (ostream& out,vector<T>a){
    out<<'[';
    for(auto x:a)out<<x<<',';
    return out<<']';
}
template<class T>
auto ary(T *a,int l,int r){
    return vector<T>{a+l,a+1+r};
}
template<class T>
void debug(T x){
    cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
    cerr<<x<<' ',debug(y...);
}
#else
#define debug(...) void()
#endif
const int N=3e5+10,V=50;
int n,a[N],b[N];
int mn[N<<2],mx[N<<2],laz[N<<2];
int tn[N<<2][V],tx[N<<2][V];
void pushup(int rt){
    mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
    mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
    memset(tn[rt],0,sizeof tn[rt]);
    memset(tx[rt],0,sizeof tx[rt]);
    for(int v:{rt<<1,rt<<1|1}){
        for(int i=0;i+mn[v]-mn[rt]<V;i++){
            tn[rt][i+mn[v]-mn[rt]]+=tn[v][i];
        }
    }
    for(int v:{rt<<1,rt<<1|1}){
        for(int i=0;mx[rt]-(mx[v]-i)<V;i++){
            tx[rt][mx[rt]-(mx[v]-i)]+=tx[v][i];
        }
    }
    mn[rt]+=laz[rt],mx[rt]+=laz[rt];
}
void build(int l=0,int r=n,int rt=1){
    if(l==r){
        mn[rt]=mx[rt]=l;
        tx[rt][0]=tn[rt][0]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int L,int R,int x,int l=0,int r=n,int rt=1){
    if(L<=l&&r<=R){
        mx[rt]+=x,mn[rt]+=x,laz[rt]+=x;
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)update(L,R,x,l,mid,rt<<1);
    if(mid<R)update(L,R,x,mid+1,r,rt<<1|1);
    pushup(rt);
}
void query(int *t,int L,int R,int vl,int vr,int l=0,int r=n,int rt=1,int s=0){
    if(R<l||r<L||mx[rt]+s<vl||vr<mn[rt]+s)return;
    if(L<=l&&r<=R&&max(vl,mn[rt]+s+V)>min(vr,mx[rt]+s-V)){
        int i;
        for(i=max(mn[rt]+s,vl);i<=min(mn[rt]+s+V-1,vr);i++){
            t[i]+=tn[rt][i-mn[rt]-s];
        }
        for(i=max(i,mx[rt]+s-V+1);i<=min(vr,mx[rt]+s);i++){
            t[i]+=tx[rt][mx[rt]+s-i];
        }
        return;
    }
    int mid=(l+r)>>1;
    s+=laz[rt];
    query(t,L,R,vl,vr,l,mid,rt<<1,s);
    query(t,L,R,vl,vr,mid+1,r,rt<<1|1,s);
}
void range(int L,int R,int &vl,int &vr,int l=0,int r=n,int rt=1,int s=0){
    if(R<l||r<L)return;
    if(L<=l&&r<=R){
        vl=min(vl,mn[rt]+s);
        vr=max(vr,mx[rt]+s);
        return;
    }
    int mid=(l+r)>>1;
    s+=laz[rt];
    range(L,R,vl,vr,l,mid,rt<<1,s);
    range(L,R,vl,vr,mid+1,r,rt<<1|1,s);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[a[i]]=i;
    build();
    ll cur=n*(n+1ll)/2,ans=cur*n;
    for(int w=n;w>1;w--){
        int i=b[w];
        int l1=INT_MAX,r1=INT_MIN;
        range(0,i-1,l1,r1);
        int l2=INT_MAX,r2=INT_MIN;
        range(i,n,l2,r2);
        int l=max(l1,l2-1),r=min(r1+1,r2);
        if(l<=r){
            static int tl[N+N],tr[N+N];
            // static int s[N];
            // for(int i=1;i<=n;i++){
            //     s[i]=s[i-1]+(a[i]>w?-1:1);
            // }
            // debug(ary(s,1,n));
            query(tl+N,0,i-1,l,r);
            query(tr+N,i,n,l,r);
            // debug(i,l,r,ary(tl,l,r),ary(tr,l,r));
            for(int i=l;i<=r;i++){
                cur-=1ll*tl[N+i]*tr[N+i];
            }
            for(int i=l;i<r;i++){
                cur-=1ll*tl[N+i]*tr[N+i+1];
            }
            for(int i=l;i<=r;i++){
                tl[N+i]=tr[N+i]=0;
            }
            update(i,n,-2);
        }
        ans-=cur;
        // debug(w,cur);
    }
    printf("%lld\n",ans);
    return 0;
}