#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

const int maxn=3e5+10;
int n;
int p[maxn];
const int lim=700;
int t[lim*2+10],pos[maxn];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i],pos[p[i]]=i;
    ll ans=0;
    for(int w=1;w<=n;w++){
        int i=p[w];
        fill(t,t+lim*2+10,0);
        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(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}