#include <bits/stdc++.h>
namespace IO {
template <typename T>
inline void read(T &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  x *= f;
  return;
}
template <typename T>
inline void write(T x = 0) {
  T wr[51];
  wr[0] = 0;
  if (x < 0) putchar('-'), x = -x;
  if (!x) putchar(48);
  while (x) wr[++wr[0]] = x % 10, x /= 10;
  while (wr[0]) putchar(48 + wr[wr[0]--]);
  return;
}
}  // namespace IO
using IO::read;
using IO::write;
using namespace std;
const int N = 1e6 + 11, mod1 = 998244353, mod0 = 1e9 + 7, bas0 = 19260817,
          bas1 = 19491001;
int n;
int a[N];
int b[N][3], v0, v1;
long long ans;
int c[N], p[N], q[N];
pair<int, int> d[N];
map<pair<int, int>, int> cnt;
int main() {
  b[0][0] = b[0][1] = 1;
  scanf("%d", &n);
  for (register int i = 1; i <= n; ++i)
    b[i][0] = 1ll * b[i - 1][0] * bas0 % mod0,
    b[i][1] = 1ll * b[i - 1][1] * bas1 % mod1;
  cnt[d[0] = make_pair(0, 0)]++;
  int j = 0;
  for (register int i = 1; i <= n; ++i) {
    read(a[i]);
    v0 = (0ll + v0 - 1ll * b[a[i]][0] * c[a[i]] % mod0) % mod0;
    v1 = (0ll + v1 - 1ll * b[a[i]][1] * c[a[i]] % mod1) % mod1;
    c[a[i]]++;
    c[a[i]] %= 3;
    ++p[a[i]];
    v0 = (0ll + v0 + 1ll * b[a[i]][0] * c[a[i]] % mod0) % mod0;
    v1 = (0ll + v1 + 1ll * b[a[i]][1] * c[a[i]] % mod1) % mod1;
    if (v0 < 0) v0 += mod0;
    if (v1 < 0) v1 += mod1;
    d[i] = make_pair(v0, v1);
    while (p[a[i]] - q[a[i]] > 3) {
      --cnt[d[j]];
      ++j;
      ++q[a[j]];
    }
    ans += cnt[d[i]];
    cnt[make_pair(v0, v1)]++;
  }
  cout << ans << endl;
  return 0;
}
