#include <bits/stdc++.h>
using namespace std;
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
const int N = 1e6 + 10;
const long long MOD = 1e9 + 7;
const long long p1 = 57, M1 = 1e9 + 3;
const int rx[4] = {-1, 0, 1, 0};
const int ry[4] = {0, 1, 0, -1};
const int hx[8] = {-2, -2, -1, 1, 2, 2, 1, -1};
const int hy[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
const long double eps = 1e-7;
const double pi = acos(-1.0);
const long long INF = 1e14 + 1000;
struct segtree {
  vector<pair<int, int> > t;
  vector<int> lazy;
  int nw;
  segtree(int n) {
    nw = (1 << (32 - __builtin_clz(n) - (__builtin_popcount(n) == 1)));
    t.resize(nw << 1, {0, 1});
    lazy.resize(nw << 1);
    for (int i = nw - 1; i > 0; i--) {
      t[i].second = t[i * 2].second + t[i * 2 + 1].second;
    }
  }
  void push(int v) {
    t[v * 2].first += lazy[v];
    t[v * 2 + 1].first += lazy[v];
    lazy[v * 2] += lazy[v];
    lazy[v * 2 + 1] += lazy[v];
    lazy[v] = 0;
  }
  void upd(int v, int cl, int cr, int l, int r, int x) {
    if (cl >= l && cr <= r) {
      t[v].first += x;
      lazy[v] += x;
      return;
    }
    if (cl >= r || cr <= l) return;
    push(v);
    int mid = (cl + cr) / 2;
    upd(v * 2, cl, mid, l, r, x);
    upd(v * 2 + 1, mid, cr, l, r, x);
    if (t[v * 2].first < t[v * 2 + 1].first) {
      t[v] = t[v * 2];
    } else if (t[v * 2 + 1].first < t[v * 2].first) {
      t[v] = t[v * 2 + 1];
    } else {
      t[v] = t[v * 2];
      t[v].second += t[v * 2 + 1].second;
    }
  }
  void upd(int l, int r, int x) { upd(1, 1, nw + 1, l, r + 1, x); }
  int kol(int v, int cl, int cr, int l, int r) {
    if (cl >= l && cr <= r) {
      if (t[v].first == 0)
        return t[v].second;
      else
        return 0;
    }
    if (cl >= r || cr <= l) return 0;
    push(v);
    int mid = (cl + cr) / 2;
    return kol(v * 2, cl, mid, l, r) + kol(v * 2 + 1, mid, cr, l, r);
  }
  int kol(int l, int r) { return kol(1, 1, nw + 1, l, r + 1); }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
  }
  vector<int> pos[n];
  long long res = 0;
  segtree sgt(n);
  for (int i = 0; i < n; i++) {
    pos[a[i]].push_back(i);
    int sz = pos[a[i]].size();
    if (sz == 1) {
      sgt.upd(1, i + 1, 1);
    } else if (sz == 2) {
      sgt.upd(1, pos[a[i]][0] + 1, -1);
      sgt.upd(1, i + 1, 1);
    } else if (sz == 3) {
      sgt.upd(1, pos[a[i]][1] + 1, -1);
      sgt.upd(pos[a[i]][0] + 2, i + 1, 1);
    } else if (sz == 4) {
      sgt.upd(pos[a[i]][0] + 2, pos[a[i]][2] + 1, -1);
      sgt.upd(1, pos[a[i]][0] + 1, 1);
      sgt.upd(pos[a[i]][1] + 2, i + 1, 1);
    } else {
      sgt.upd(1, pos[a[i]][sz - 5] + 1, -1);
      sgt.upd(pos[a[i]][sz - 4] + 2, pos[a[i]][sz - 2] + 1, -1);
      sgt.upd(1, pos[a[i]][sz - 4] + 1, 1);
      sgt.upd(pos[a[i]][sz - 3] + 2, i + 1, 1);
    }
    res += sgt.kol(1, i + 1);
  }
  cout << res << '\n';
  return 0;
}
