// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
void fast_io(){
// freopen("", "r", stdin);
// freopen("", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(); cout.tie();
cout << setprecision(9);
}
#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
const int N = 2e5 + 5;
int n, rep, A[N];
vector<int> idx[N];
int calculate(int I){
int ans = 0, m = idx[I].size(), sum = 0;
int after = m, before = 0;
vector<int> a;
int init = idx[I][0] - 1;
if (init > after){
a.push_back(after - init);
}
for (int i = 0; i < min(init, after); i++){
a.push_back(-1);
}
a.push_back(1);
after--, before++;
for (int i = 1; i < m; i++){
if (idx[I][i] - idx[I][i - 1] - 1 == 0){
a.push_back(1);
}
else {
int total = idx[I][i] - idx[I][i - 1] - 1;
int furth = min(total, after);
total -= furth;
int behin = min(total, before);
total -= behin;
for (int j = 0; j < behin; j++) a.push_back(-1);
if (total != 0) a.push_back(-total);
for (int j = 0; j < furth; j++) a.push_back(-1);
a.push_back(1);
}
after--, before++;
}
init = n - idx[I].back();
before = m;
int prev = min(init, before);
init -= prev;
for (int i = 0; i < prev; i++) a.push_back(-1);
if (init > 0) a.push_back(-init);
m = a.size();
int s = 0;
ordered_set S;
S.insert(0);
for (int i = 0; i < m; i++){
s += a[i];
ans += S.order_of_key(s);
S.insert(s);
}
return ans;
}
void solve() {
cin >> n;
map<int, int> c;
for (int i = 1; i <= n; i++){
cin >> A[i];
if (c[A[i]]) A[i] = c[A[i]];
else {
c[A[i]] = ++rep;
A[i] = rep;
}
idx[A[i]].push_back(i);
}
int ans = 0;
for (int i = 1; i <= n; i++){
// cout << calculate(i) << endl;
if (idx[i].size() == 0) continue;
ans += calculate(i);
}
cout << ans << endl;
return;
}
signed main() {
fast_io();
srand(chrono::steady_clock::now().time_since_epoch().count());
int tc = 1;
// cin >> tc;
while (tc--) solve();
return 0;
}
