// is sqrt intended
// and is n^1.5 log^0.5 n intended
// i guess the tl is 3sec so
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int hi(int a, int b, int c, int d, int e) {
// [a,b] + [c,d] <= e.
if(b-a<=d-c) {swap(a,c);swap(b,d);}
if(e<a+c) return 0;
if(e>b+d) return (b-a+1)*(d-c+1);
if(e<=a+d) return (e-a-c+1)*(e-a-c+2)/2;
if(e>=b+c) return (b-a+1)*(d-c+1)-(b+d-e)*(b+d+1-e)/2;
return (e-a-d) * (d-c+1) + (d-c+1) * (d-c+2) / 2;
}
int calcA(int n, vector<int> &v) {
int s = v.size(), ans = 0;
for(int i=0;i<s;i++) for(int j=i;j<s;j++) {
int l = (i?v[i-1]+1:0);
int r = (j==s-1?n-1:v[j+1]-1);
ans += hi(-v[i],-l,v[j],r,(j-i)<<1);
}
return ans;
}
// 2pre[r] - r > 2pre[l] - l
struct fenwick {
int n; vector<int> fw;
fenwick(int _n): n(_n), fw(_n+1,0) {}
inline void up(int x) {for(;x<=n;x+=(x&(-x))) ++fw[x];}
inline int qry(int x) {
int ans = 0;
for(;x;x-=(x&(-x))) ans+=fw[x];
return ans;
}
};
int calcB(int n, vector<int> &v) {
fenwick fw(n<<1|1);
fw.up(n+1);
int a[n]; fill(a,a+n,-1); for(auto i: v) a[i]=1;
int ans = 0;
for(int i=0,s=0;i<n;i++) {
s += a[i];
ans += fw.qry(s+n);
fw.up(s+n+1);
}
return ans;
}
main() {
int n; cin >> n;
int a[n], b[n]; for(int i=0;i<n;i++) {cin>>a[i];b[i]=a[i];}
sort(b,b+n);
for(int i=0;i<n;i++) a[i]=lower_bound(b,b+n,a[i])-b;
vector<int> v[n];
for(int i=0;i<n;i++) v[a[i]].push_back(i);
int ans = 0;
for(int i=0;i<n;i++) {
/*
if(calcA(n,v[i]) != calcB(n,v[i])) {
for(auto j: v[i]) cout << j << " "; cout << "\n";
cout << calcA(n,v[i]) << " " << calcB(n,v[i]);
return -1;
}
*/
ans += (v[i].size()<=800?calcA(n,v[i]):calcB(n,v[i]));
}
cout << ans;
}
