#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int maxn=3e5+9;
int n,a[maxn],p[maxn];
int val[maxn];
ll cnt[maxn*2+9];
ll &get(int k) { return cnt[k+maxn]; }
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i],p[a[i]]=i,val[i]=1;
    ll res=0;
    for(int v=1;v<=n;++v)
    {
        int pos=p[v];
        int MAXL;
        int dis=abs(v-n/2);
        if(dis<1) dis=1;
        MAXL=1ll*n*n/(long long)(powl(dis,1.65));
        if(MAXL<30) MAXL=30;
        if(MAXL>n) MAXL=n;
        int l=pos-MAXL,r=pos+MAXL;
        if(l<1) l=1;
        if(r>n) r=n;
        ll ans=0;
        int sl=0,sr=0;
        val[pos]=-1;
        for(int i=pos;i>=l;--i)
        {
            sl+=val[i];
            // printf("sl=%d\n",sl);
            get(sl)++;
        }
        for(int j=pos;j<=r;++j)
        {
            sr+=val[j];
            // printf("sr=%d\n",sr);
            // sl+sr-2val[pos]=0/1
            // sl=0/1+2val[pos](-2)-sr
            ans+=get(-2-sr)+get(-1-sr);
        }
        res+=1ll*ans*v;
        // printf("%d %lld\n",v,ans);
        get(0)=0;
        for(int s=-1;;--s)
        {
            if(!get(s)) break;
            get(s)=0;
        }
        for(int s=1;;++s)
        {
            if(!get(s)) break;
            get(s)=0;
        }
    }
    cout<<res<<endl;
}