#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define mp make_pair
#define next ___next
#define prev ___prev
#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define __builtin_popcount __builtin_popcountll
#define sz(x) (int32_t)(x.size())
#define all(x) x.begin(), x.end()
#define mem(f, x) memset(f, x, sizeof(f))
#define FOR(i, l, r) for (int32_t i = (l); i <= (r); ++i)
#define REP(i, l, r) for (int32_t i = (l); i < (r); ++i)
#define FORD(i, r, l) for (int32_t i = (r); i >= (l); --i)
#define REPD(i, r, l) for (int32_t i = (r - 1); i >= (l); --i)
using ll = long long;
using ld = long double;
template<class A, class B> bool mini(A &a, const B &b) {return a > b ? (a = b, true) : false;};
template<class A, class B> bool maxi(A &a, const B &b) {return a < b ? (a = b, true) : false;};
template<class T> T Abs(const T &x) {return (x < 0 ? -x : x);}
constexpr int MOD = 1e9 + 7; // 998244353
template<class X, class Y> void add(X &x, const Y &y) {x = (x + y); if (x >= MOD) x -= MOD;}
template<class X, class Y> void sub(X &x, const Y &y) {x = (x - y); if (x < 0) x += MOD;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
/* Author: Phan */
/** END OF TEMPLATE. **/
int const mxN = 2e5 + 5, up = 2e5 + 1, S = 447;
int n;
int a[mxN];
bool light[mxN];
vector <int> s[mxN];
struct Fenwick {
int n; int s[mxN << 1];
Fenwick(int _n = up): n(_n) {};
void reset(void) {
mem(s, 0);
}
void update(int i, int x) {
for (; i <= n; i += (i & (-i))) {
s[i] += x;
}
}
int get(int i) {
int res = 0;
for (; i > 0; i -= (i & (-i))) {
res += s[i];
}
return res;
}
void add(int i) {
update(i, 1);
}
void del(int i) {
update(i, -1);
}
};
int32_t main(void) {
cin.tie(nullptr) -> sync_with_stdio(false);
cin >> n;
vector <int> nen;
FOR(i, 1, n) {
cin >> a[i];
nen.emplace_back(a[i]);
}
sort(all(nen)); nen.erase(unique(all(nen)), nen.end());
FOR(i, 1, n) {
a[i] = lower_bound(all(nen), a[i]) - nen.begin() + 1;
s[a[i]].emplace_back(i);
}
int res = 0;
Fenwick bit;
auto heavy = [&](int i) {
bit.reset();
bit.add(up);
int j = 0, cur = up;
FOR(i, 1, n) {
if (j < sz(s[i]) && i == s[i][j]) {
j++;
cur++;
} else {
cur--;
}
res += bit.get(cur - 1);
bit.add(cur);
}
};
FOR(i, 1, sz(nen)) {
if (sz(s[i]) <= S) {
light[i] = 1;
} else {
heavy(i);
}
}
auto process = [&](void) {
vector <int> val;
vector <int> cnt(sz(nen) + 1);
FOR(i, 1, n) {
int len = min(n - i + 1, 2 * S - 1), mx = 0;
FOR(j, 1, len) {
int r = i + j - 1;
if (light[a[r]] == 0) continue;
val.emplace_back(a[r]);
cnt[a[r]]++;
maxi(mx, cnt[a[r]]);
if (mx * 2 > j) res++;
}
for (int &x : val) cnt[x] = 0;
val.clear();
}
};
process();
cout << res;
}
