#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
signed main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> arr(n), cnt(n), ccnt(n);
  vector<unsigned long long> r1(n), r2(n), h(n + 1);
  for (int i = 0; i < n; i++)
    cin >> arr[i], arr[i]--, r1[i] = rng(), r2[i] = rng();
  int l = 0;
  map<unsigned long long, long long> m;
  m[0]++;
  long long res = 0;
  for (int i = 0; i < n; i++) {
    for (ccnt[arr[i]]++; ccnt[arr[i]] > 4; l++) m[h[l]]--, ccnt[arr[l]]--;
    h[i + 1] = h[i];
    if (cnt[arr[i]] % 3 != 1) h[i + 1] ^= r2[arr[i]];
    if (cnt[arr[i]] % 3 != 2) h[i + 1] ^= r1[arr[i]];
    cnt[arr[i]]++;
    res += m[h[i + 1]]++;
  }
  cout << res << "\n";
}
