#include <bits/stdc++.h>
using namespace std;
int main() {
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  long long n;
  cin >> n;
  vector<long long> a(n + 1), po(n + 1), cnt(n + 1, 0);
  for (long long i = 1; i <= n; i++) cin >> a[i];
  unordered_map<long long, long long> mp;
  vector<long long> Hash(n + 1);
  for (long long i = 1; i <= n; i++) {
    po[i] = ((long long)rand() << 32) + (rand() << 16) + rand();
  }
  long long ptr = 1, temp_hash = 0, final_ans = 0;
  vector<long long> pos[n + 1];
  mp[0] = 1;
  long long once = 0;
  for (long long i = 1; i <= n; i++) {
    pos[a[i]].push_back(i);
    long long temp_size = pos[a[i]].size(), req_pos;
    if (temp_size >= 4) {
      if (once == 0) {
        once = 1;
        mp[0]--;
      }
      req_pos = pos[a[i]][temp_size - 4];
      for (long long j = ptr; j < req_pos; j++) {
        if (mp[Hash[j]]) mp[Hash[j]]--;
      }
      ptr = max(ptr, req_pos);
    }
    temp_hash = ((temp_hash - (po[a[i]] * cnt[a[i]])) % 100055128505716009 +
                 2 * 100055128505716009) %
                100055128505716009;
    cnt[a[i]]++;
    cnt[a[i]] %= 3;
    temp_hash = (temp_hash + (po[a[i]] * cnt[a[i]])) % 100055128505716009;
    Hash[i] = temp_hash;
    final_ans = (final_ans + mp[Hash[i]]);
    mp[Hash[i]]++;
  }
  cout << final_ans << endl;
  return 0;
}
