#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=1e4+7; int n; int p[maxn],inv[maxn]; int a[maxn]; int L[maxn<<2]; int R[maxn<<2]; signed main(){ cin>>n; for(int i=1;i<=n;i++)cin>>p[i],inv[p[i]]=i; int Ans=0; for(int i=1;i<=n;i++){ int ps=inv[i]; a[ps]=0; for(int j=1;j<=n;j++){ if(p[j]<i)a[j]=-1; else if(p[j]>i) a[j]=1; } int S=0; for(int j=ps;j>=1;j--){ S+=a[j]; L[S+n]+=j; }S=0; for(int j=ps;j<=n;j++){ S+=a[j]; R[S+n]+=j; } int Sum=0; for(int i=0;i<=n*2;i++)Sum+=L[i]*R[2*n-i],L[i]=R[2*n-i]=0; Ans+=Sum*i; } cout<<Ans<<endl; return 0; }