#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ppi pair<pair<int, int>>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define OK cout << "OK" << '\n'
#define qi queue<int>
#define sti stack<int>
#define si stack<int>
#define yes cout << "Yes" << '\n'
#define no cout << "No" << '\n'
#define pb push_back
#define eb emplace_back
#define vpi vector<pair<int, int>>
#define ll long long
#define nl cout << '\n'
#define ok cout << "OK" << '\n'
#define mp make_pair
#define repr(i, b, a) for (int i = b; i >= a; i--)
#define veb vector<bool>
#define vveb vector<vector<bool>>
#define int long long
void printvec(vi v)
{
rep(i, 1, v.size()-1) cout << v[i] << ' '; nl;
}
long long binpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
long long binpowmod(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
void compress(vi &a)
{
int n = a.size() - 1;
vpi pairs(n+1);
rep(i, 1, n) pairs[i] = mp(a[i],i);
sort(pairs.begin(), pairs.end());
int c = 1;
rep(i, 1, n)
{
if (pairs[i].first > pairs[i-1].first && i > 1) c++;
a[pairs[i].second] = c;
}
return;
}
// PROGRAM
const int MOD = (int)1e9 + 7;
void build(int v, int l, int r, vi &a, vi &seg, vi &seg_val)
{
// cout << v << " " << l << ' ' << r << endl;
if (l == r)
{
return;
}
int mid = (l + r)/2;
build(v<<1, l, mid, a, seg, seg_val);
build((v<<1) + 1, mid + 1, r, a, seg, seg_val);
vi vec;
rep(i, l - 1, mid - 1) vec.pb(a[i]);
sort(vec.begin(), vec.end());
int curr_res = 0;
rep(i, mid + 1, r)
{
auto it = lower_bound(vec.begin(), vec.end(), a[i]);
curr_res += it - vec.begin();
}
seg_val[v] = curr_res + seg_val[v<<1] + seg_val[(v<<1)+1];
}
void solve()
{
// CHECK IF PROGRAM HAS TESTCASES
int n; cin >> n;
vi a(n+1);
rep(i, 1, n) cin >> a[i];
compress(a);
int mx = -1;
rep(i, 1, n) mx = max(mx, a[i]);
int res = 0;
rep(c, 1, mx)
{
vi b(n+1);
rep(i, 1, n)
{
if (a[i] == c) b[i] = 1;
else b[i] = 0;
}
vi pf(n+1);
rep(i, 1, n) pf[i] = pf[i-1] + b[i];
rep(i, 1, n) b[i] = 2*pf[i] - i;
vi seg_val(4*n+10);
vi seg(4*n+10);
build(1, 1, n, b, seg, seg_val);
res += seg_val[1] + pf[n];
}
cout << res << '\n';
}
int32_t main()
{
//fastio
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//fastio
int T = 1;
//cin >> T;
while (T--) solve();
}
