#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
#define base 267LL
#define mod 1000'000'000'000'000'003LL
#define FOR(i,a,b) for(int i = a; i < b; i++)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll gen(ll l, ll r){
    return uniform_int_distribution<ll>(1, LLONG_MAX - 1)(rng);
}
ll mul(ll a, ll b){
    __int128_t v = a;
    return v * b % mod;
}
void solve() {
    ll n;
    cin >> n;
    vector <ll> l1(n);
    vector <vector <ll>> adj(n+1);
    vector <ll> pow(n+1);
    vector <ll> cnt(n+1, 0);
    pow[0] = 1;
    for (int i = 1; i <= n; i++){
        pow[i] = mul(pow[i-1], base);
    }
    ll answ = 0;
    ll lo = -1; ll v = 0;
    map <ll,vector <ll>> f;
    FOR(i,0,n) cin >> l1[i];
    f[0].push_back(-1);
    FOR(i,0,n){
        adj[l1[i]].push_back(i);
        v -= mul(cnt[l1[i]],pow[l1[i]]);
        cnt[l1[i]] = (cnt[l1[i]] + 1) % 3;
        v = ((v + mul(cnt[l1[i]], pow[l1[i]])) % mod + mod) % mod;
        if (adj[l1[i]].size() > 3){
            ll sz = adj[l1[i]].size();
            lo = max(lo, adj[l1[i]][sz - 4]);
        }
        auto cur = &f[v];
        auto it = lower_bound(cur->begin(), cur->end(), lo);
        ll pos = it - cur->begin();
        answ += cur->size() - pos;
        f[v].push_back(i);
    }
    cout << answ << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll t = 1;
    while (t--) {
        solve();
    }

    return 0;
}