#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=1000;
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];
        memset(t,0,sizeof t);
        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+=(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;
}