#include <bits/stdc++.h>
using namespace std;
const int N = 60;
array<int, N> operator^(const array<int, N> &a, const array<int, N> &b) {
  array<int, N> c;
  for (int i = 0; i < N; i++) {
    c[i] = a[i] + b[i];
    if (c[i] >= 3) c[i] -= 3;
  }
  return c;
}
mt19937 rnd(0);
int n;
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    --a[i];
  }
  vector<array<int, N>> nums(n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < N; j++) {
      nums[i][j] = rnd() % 3;
    }
  }
  vector<vector<int>> pos(n);
  vector<array<int, N>> pr(1);
  map<array<int, N>, int> cnt;
  cnt[pr[0]] = 1;
  int cur = 0;
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    pr.push_back(pr.back() ^ nums[a[i]]);
    pos[a[i]].push_back(i);
    if (pos[a[i]].size() >= 4) {
      while (cur <= pos[a[i]][int(pos[a[i]].size()) - 4]) {
        --cnt[pr[cur]];
        ++cur;
      }
    }
    ans += cnt[pr.back()];
    ++cnt[pr.back()];
  }
  cout << ans << endl;
  return 0;
}
