#include <bits/stdc++.h>
const int MAX_N = 500000;
int lazy[1 + 4 * MAX_N];
int aint[1 + 4 * MAX_N], cnt[1 + 4 * MAX_N];
void build(int l = 1, int r = MAX_N, int nod = 1) {
  if (l == r)
    cnt[nod] = 1;
  else {
    int mid = (l + r) / 2;
    build(l, mid, 2 * nod);
    build(mid + 1, r, 2 * nod + 1);
    cnt[nod] = cnt[2 * nod] + cnt[2 * nod + 1];
  }
}
void pushlazy(int l, int r, int nod) {
  aint[nod] += lazy[nod];
  if (l < r) {
    lazy[2 * nod] += lazy[nod];
    lazy[2 * nod + 1] += lazy[nod];
  }
  lazy[nod] = 0;
}
void combine(int nod) {
  aint[nod] = aint[2 * nod];
  cnt[nod] = cnt[2 * nod];
  if (aint[nod] == aint[2 * nod + 1])
    cnt[nod] += cnt[2 * nod + 1];
  else if (aint[2 * nod + 1] < aint[nod]) {
    aint[nod] = aint[2 * nod + 1];
    cnt[nod] = cnt[2 * nod + 1];
  }
}
void update(int i, int j, int val, int l = 1, int r = MAX_N, int nod = 1) {
  pushlazy(l, r, nod);
  if (r < i || j < l || j < i) return;
  if (i <= l && r <= j) {
    lazy[nod] += val;
    pushlazy(l, r, nod);
  } else {
    int mid = (l + r) / 2;
    update(i, j, val, l, mid, 2 * nod);
    update(i, j, val, mid + 1, r, 2 * nod + 1);
    combine(nod);
  }
}
int query(int i, int j, int l = 1, int r = MAX_N, int nod = 1) {
  pushlazy(l, r, nod);
  if (j < l || r < i || j < i) return 0;
  if (i <= l && r <= j)
    return cnt[nod] * (aint[nod] == 0);
  else {
    int mid = (l + r) / 2;
    return query(i, j, l, mid, 2 * nod) + query(i, j, mid + 1, r, 2 * nod + 1);
  }
}
int v[1 + MAX_N], next[1 + MAX_N], last[1 + MAX_N];
int main() {
  int n;
  scanf("%d", &n);
  build();
  long long res = 0LL;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &v[i]);
    next[i] = last[v[i]];
    last[v[i]] = i;
    update(next[i] + 1, i, 1);
    int pnt = next[next[i]];
    if (pnt != 0) update(next[pnt] + 1, pnt, -1);
    pnt = next[next[next[i]]];
    if (pnt != 0) update(next[pnt] + 1, pnt, 1);
    res = res + query(1, i);
  }
  printf("%lld", res);
  return 0;
}
