#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define mpr make_pair
#define fi first
#define se second
#define db double
// #define int long long

char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p1=buf,p2=buf+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
void read(int&x){
    char c=GC;x=0;
    while(!isdigit(c))c=GC;
    while(isdigit(c))x=x*10+c-'0',c=GC;
}

const int maxn=3e5+10;
int n;
int p[maxn];
const int lim=900;
int t[lim*2+10],pos[maxn];

void solve(){
    read(n);
    for(int i=1;i<=n;i++)read(p[i]),pos[p[i]]=i;
    ll ans=0;
    for(int w=1;w<=n;w++){
        int i=p[w];
        int cur=lim;
        for(int r=w;r<=n;r++){
            cur+=(p[r]>p[w]?1:-1);
            if(cur<0||cur>lim*2)break;
            t[cur]++;
        }
        cur=1+lim;
        for(int l=w;l;l--){
            cur+=(p[l]>p[w]?1:-1);
            if(cur<2||cur>lim*2-2)break;
            ans+=1ll*(t[lim*2-cur]+t[lim*2-cur-1])*i;
        }
    }
    cout<<ans<<"\n";
    
}
signed main(){
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}