#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(func %s, line #%d): " fmt,__func__,__LINE__,##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=3e5+5,B=1000;
inline int read(){
  char ch=getchar();int x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
int n,p[N],pos[N],a[N];
int sum[N],cnt1[B<<1],cnt2[B<<1];
signed LJY(){
  n=read();For(i,1,n) pos[p[i]=read()]=i;
  ll ans=0;For(i,1,n) a[i]=-1;
  ForDown(i,n,1){
    memset(cnt1,0,sizeof(cnt1));
    memset(cnt2,0,sizeof(cnt2));
    cnt1[B]=cnt2[B]=1;int s=B;
    For(j,pos[i]+1,n){
      s+=a[j];
      if(s<0||s>=(B<<1)) break;
      cnt1[s]++;
    }s=B;
    ForDown(j,pos[i]-1,1){
      s+=a[j];
      if(s<0||s>=(B<<1)) break;
      cnt2[s]++;
    }a[pos[i]]=1;
    ll tot=0;
    For(i,1,(B<<1)-1) tot+=(ll)cnt1[i]*(cnt2[(B<<1)-i]+cnt2[(B<<1)-i+1]);
    ans+=tot*i;
  }printf("%lld",ans);
  return 0;
}