#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500100;
const long long INF = 0x3f3f3f3f;
struct seg {
  seg *fe, *fd;
  long long meio, l, r, mex, lazy, q;
  seg(long long x, long long y) {
    l = x, r = y;
    meio = (x + y) / 2;
    mex = lazy = 0;
    q = r - l + 1;
    if (l == r) return;
    fe = new seg(x, meio);
    fd = new seg(meio + 1, y);
  }
  void lazyup() {
    if (lazy == 0) return;
    mex += lazy;
    if (l != r) fe->lazy += lazy, fd->lazy += lazy;
    lazy = 0;
  }
  void up(long long a, long long b, long long novo) {
    lazyup();
    if (l >= a && r <= b) {
      lazy += novo;
      lazyup();
      return;
    }
    if (l > b || r < a) return;
    fe->up(a, b, novo), fd->up(a, b, novo);
    mex = max(fe->mex, fd->mex);
    if (fe->mex == fd->mex)
      q = fe->q + fd->q;
    else if (fe->mex > fd->mex)
      q = fe->q;
    else
      q = fd->q;
  }
  pair<long long, long long> get(long long a, long long b) {
    lazyup();
    if (l >= a && r <= b) return {mex, q};
    if (l > b || r < a) return {-INF, 0};
    pair<long long, long long> re = fe->get(a, b), rd = fd->get(a, b);
    if (re.first == rd.first) return {re.first, re.second + rd.second};
    if (re.first > rd.first) return re;
    return rd;
  }
};
vector<long long> vec[MAXN];
long long L[MAXN], R[MAXN];
long long v[MAXN];
long long pos[MAXN];
seg m0(1, MAXN), m1(1, MAXN), m2(1, MAXN);
signed main() {
  long long n;
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> v[i];
  for (long long i = n; i >= 1; i--) {
    long long x = v[i];
    long long h = vec[x].size();
    pos[i] = h;
    if (h < 3)
      R[i] = n + 1;
    else
      R[i] = vec[x][h - 3] - 1;
    if (h < 2)
      L[i] = n + 1;
    else
      L[i] = vec[x][h - 2];
    vec[x].push_back(i);
  }
  long long resp = 0;
  for (long long i = n; i >= 1; i--) {
    m0.up(i, i, -1), m0.up(L[i], R[i], 1);
    m1.up(i, i, -1), m1.up(L[i], R[i], 1);
    m2.up(i, i, -1), m2.up(L[i], R[i], 1);
    if (pos[i] > 0) {
      long long at = vec[v[i]][pos[i] - 1];
      m0.up(L[at], R[at], -1);
      m1.up(L[at], R[at], -1);
      m2.up(L[at], R[at], -1);
    }
    if (i % 3 == 0) m0.up(i + 3, n + 3, -1);
    if (i % 3 == 1) m1.up(i + 3, n + 3, -1);
    if (i % 3 == 2) m2.up(i + 3, n + 3, -1);
    pair<long long, long long> a;
    if (i % 3 == 0) a = m0.get(i, n);
    if (i % 3 == 1) a = m1.get(i, n);
    if (i % 3 == 2) a = m2.get(i, n);
    if (a.first == 0) resp += a.second;
  }
  cout << resp << endl;
}
