#include <bits/stdc++.h>
using namespace std;
template <typename T>
void out(T x) {
  cout << x << endl;
  exit(0);
}
using ll = long long;
const ll mod = 1e9 + 7;
const int maxn = 1e6 + 5;
const ll inf = 1e9;
struct node {
  ll minValue;
  int count;
  node() {
    minValue = 0;
    count = 1;
  }
  node(ll val) {
    minValue = val;
    count = 1;
  }
};
node merge(node a, node b) {
  if (a.minValue < b.minValue) {
    return a;
  }
  if (a.minValue > b.minValue) {
    return b;
  }
  assert(a.minValue == b.minValue);
  a.count += b.count;
  return a;
}
struct MinLazySegmentTree {
  vector<node> t;
  vector<ll> o;
  void init(int n) {
    n += 10;
    t.resize(4 * n);
    o.resize(4 * n);
  }
  void push(int v) {
    t[2 * v].minValue += o[v];
    t[2 * v + 1].minValue += o[v];
    o[2 * v] += o[v];
    o[2 * v + 1] += o[v];
    o[v] = 0;
  }
  node queryMin(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl) return node(inf);
    if (l <= tl && tr <= r) {
      return t[v];
    } else {
      push(v);
      int tm = (tl + tr) / 2;
      return merge(queryMin(2 * v, tl, tm, l, r),
                   queryMin(2 * v + 1, tm + 1, tr, l, r));
    }
  }
  void rangeAdd(int v, int tl, int tr, int l, int r, ll dx) {
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r) {
      t[v].minValue += dx;
      o[v] += dx;
    } else {
      push(v);
      int tm = (tl + tr) / 2;
      rangeAdd(2 * v, tl, tm, l, r, dx);
      rangeAdd(2 * v + 1, tm + 1, tr, l, r, dx);
      t[v] = merge(t[2 * v], t[2 * v + 1]);
    }
  }
};
int n;
int a[maxn];
ll brute() {
  ll res = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
      map<int, int> mp;
      for (int k = i; k <= j; k++) {
        if (++mp[a[k]] > 3) break;
      }
      bool ok = true;
      for (auto p : mp) {
        ok &= (p.second == 3);
      }
      res += ok;
    }
  }
  return res;
}
vector<int> inds[maxn];
MinLazySegmentTree ev;
void upd(int i, ll val) { ev.rangeAdd(1, 1, n, 1, i, val); }
ll count0(int r) {
  node res = ev.queryMin(1, 1, n, 1, r);
  ll lo = res.minValue;
  assert(lo >= 0);
  if (lo == 0) return res.count;
  return 0;
}
void print() {
  for (int i = 1; i <= n; i++) {
    cout << ev.queryMin(1, 1, n, i, i).minValue << " ";
  }
  cout << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  ev.init(n);
  ll res = 0;
  for (int i = 1; i <= n; i++) {
    inds[a[i]].push_back(i);
    upd(i, 1);
    int cnt = inds[a[i]].size();
    if (cnt >= 3) {
      if (cnt > 3) {
        upd(inds[a[i]][cnt - 4], inf);
      }
      upd(inds[a[i]][cnt - 3], -3);
    }
    ll cur = count0(i);
    res += cur;
  }
  cout << res << endl;
  return 0;
}
