#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
int n;
int a[N];
vector<int> mas[N];
vector<int> g[N];
int cnt[N], c[N];
int sum[N];
long long answ = 0;
multiset<int> L, R;
void add(int cnt, int x, int st, int lst) {
  if (cnt == 3) {
    if ((int)mas[x].size() != 0) {
      L.insert(st);
      R.insert(mas[x][0] - 1);
    }
    return;
  }
  if ((int)mas[x].size() < 3 - cnt) {
    L.insert(inf);
    R.insert(-inf);
  } else {
    L.insert(mas[x][2 - cnt]);
    R.insert((int)mas[x].size() == (3 - cnt) ? (lst - 1)
                                             : (mas[x][3 - cnt] - 1));
  }
}
void del(int cnt, int x, int lst) {
  if (cnt == 0) return;
  if ((int)mas[x].size() < 3 - cnt) {
    L.erase(L.find(inf));
    R.erase(R.find(-inf));
  } else {
    L.erase(L.find(mas[x][2 - cnt]));
    R.erase(R.find((int)mas[x].size() == (3 - cnt) ? (lst - 1)
                                                   : (mas[x][3 - cnt] - 1)));
  }
}
void solve(int l, int r) {
  if (r - l + 1 < 3) return;
  int m = (l + r) / 2;
  solve(l, m);
  solve(m + 1, r);
  int lst = r + 1;
  int s = 0;
  for (int i = m + 1; i <= r; i++) {
    c[a[i]]++;
    if (c[a[i]] == 4) {
      lst = i;
      break;
    }
    s++;
    s -= 3 * (c[a[i]] == 3);
    sum[i] = s;
    mas[a[i]].push_back(i);
    g[s].push_back(i);
  }
  L.insert(m + 1);
  R.insert(r);
  int all = 0;
  for (int i = m; i >= l; i--) {
    cnt[a[i]]++;
    if (cnt[a[i]] > 3) break;
    if (cnt[a[i]] != 1) all -= 4 - cnt[a[i]];
    all += 3 - cnt[a[i]];
    del(cnt[a[i]] - 1, a[i], lst);
    add(cnt[a[i]], a[i], m + 1, lst);
    multiset<int>::iterator it = L.end();
    --it;
    int ll = *it, rr = *R.begin();
    if (ll > rr) continue;
    ll = lower_bound(g[all].begin(), g[all].end(), ll) - g[all].begin();
    rr = upper_bound(g[all].begin(), g[all].end(), rr) - g[all].begin() - 1;
    if (ll <= rr) {
      answ += rr - ll + 1;
    }
  }
  for (int i = l; i <= m; i++) cnt[a[i]] = 0;
  for (int i = m + 1; i <= r; i++) {
    mas[a[i]].clear();
    c[a[i]] = 0;
    g[sum[i]].clear();
    sum[i] = 0;
  }
  while (!L.empty()) {
    L.erase(L.begin());
  }
  while (!R.empty()) {
    R.erase(R.begin());
  }
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  solve(1, n);
  cout << answ << endl;
  return 0;
}
