#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = (int)2e5 + 50;
int n, a[N], cnt[N];
vector<int> vec, g[N];
ll ans;
int main()
{
//ios_base::sync_with_stdio(0); cin.tie(0);
//freopen("input.txt", "r", stdin);
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
vec.pb(a[i]);
}
sort(all(vec));
vec.resize(unique(all(vec)) - vec.begin());
int m = sz(vec);
bool have[m + 1][n + 1];
for(int i = 0; i < m; i++)
for(int j = 1; j <= n; j++)
have[i][j] = 0;
for(int i = 1; i <= n; i++)
{
a[i] = lower_bound(all(vec), a[i]) - vec.begin();
cnt[a[i]]++;
have[a[i]][i] = 1;
}
for(int i = 0; i < m; i++)
{
ordered_set se;
int skok = 0;
ans += cnt[i];
for(int j = 1; j <= n; j++)
{
int add = 0;
if (have[i][j]) add++;
// if (sz(se) - se.order_of_key(j - 2 * (skok + add) + 1))
// {
// cout << i << ' ' << se.order_of_key(j - 2 * (skok + add) + 1) << '\n';
// cout << j << ' ' << skok << endl;
// }
ans += sz(se) - se.order_of_key(j - 2 * (skok + add) + 1);
se.insert(j - 2 * skok - 1);
if (have[i][j])
skok++;
}
}
cout << ans;
}
