#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;
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];
int sum[N],cnt[N<<1];
signed LJY(){
  n=read();For(i,1,n) pos[p[i]=read()]=i;
  ll ans=0;
  For(i,1,n){
    int L=pos[i],R=pos[i],s=0;
    while(L-1>0&&abs(s)<=400) s+=(p[--L]>=i?1:-1);
    s=0;while(R+1<=n&&abs(s)<=400) s+=(p[++R]>=i?1:-1);
    sum[L-1]=0;For(j,L,R) sum[j]=sum[j-1]+(p[j]>i?1:(p[j]<i?-1:0));
    ll tot=0;
    ForDown(j,R,pos[i]) cnt[sum[j]+n]++;
    For(j,L-1,pos[i]-1) tot+=cnt[sum[j]+n]+cnt[sum[j]+1+n];
    For(j,pos[i],R) cnt[sum[j]+n]=0;
    ans+=tot*i;
  }printf("%lld",ans);
  return 0;
}