#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> seg;
vector<int> lazy;
vector<vector<int>> M;
int size;
void push(int idx) {
  lazy[2 * idx] += lazy[idx];
  lazy[2 * idx + 1] += lazy[idx];
  seg[2 * idx].first += lazy[idx];
  seg[2 * idx + 1].first += lazy[idx];
  lazy[idx] = 0;
}
pair<int, int> merge(pair<int, int>& lfs, pair<int, int>& rfs) {
  if (lfs.first == rfs.first) {
    return make_pair(lfs.first, lfs.second + rfs.second);
  }
  return min(lfs, rfs);
}
void update(int idx, int l, int r, int tl, int tr, int add) {
  if (tl > tr || l > tr || r < tl)
    return;
  else if (l == tl && r == tr) {
    seg[idx].first += add;
    lazy[idx] += add;
    return;
  } else {
    push(idx);
    int tm = (tl + tr) / 2;
    update(2 * idx, l, min(r, tm), tl, tm, add);
    update(2 * idx + 1, max(tm + 1, l), r, tm + 1, tr, add);
    seg[idx] = merge(seg[2 * idx], seg[2 * idx + 1]);
  }
}
long long query(int idx, int l, int r, int tl, int tr) {
  if (tl > tr || l > tr || r < tl || seg[idx].first != 0)
    return 0;
  else if (l <= tl && r >= tr) {
    return seg[idx].second;
  } else {
    push(idx);
    int tm = (tl + tr) / 2;
    return query(2 * idx, l, r, tl, tm) + query(2 * idx + 1, l, r, tm + 1, tr);
  }
}
int get(int idx, int tl, int tr, int pos) {
  if (tl > tr || pos < tl || pos > tr)
    return -1;
  else if (tl == tr && pos == tr) {
    return seg[idx].first;
  } else {
    push(idx);
    int tm = (tl + tr) / 2;
    if (pos <= tm)
      return get(2 * idx, tl, tm, pos);
    else
      return get(2 * idx + 1, tm + 1, tr, pos);
  }
}
void build(int idx, int tl, int tr) {
  if (tl > tr)
    return;
  else if (tl == tr) {
    seg[idx] = make_pair(0, 1);
  } else {
    int tm = (tl + tr) / 2;
    build(2 * idx, tl, tm);
    build(2 * idx + 1, tm + 1, tr);
    seg[idx] = merge(seg[2 * idx], seg[2 * idx + 1]);
  }
}
int main() {
  cin >> size;
  M = vector<vector<int>>(2 * size, vector<int>(1, -1));
  seg.resize(4 * size);
  lazy.resize(4 * size);
  build(1, 0, size - 1);
  long long ret = 0;
  for (int k = 0; k < size; k++) {
    int input;
    cin >> input;
    M[input].push_back(k);
    int len = M[input].size();
    if (len >= 2) {
      update(1, M[input][len - 2] + 1, M[input][len - 1], 0, size - 1, 1);
    }
    if (len >= 4) {
      update(1, M[input][len - 4] + 1, M[input][len - 3], 0, size - 1, -1);
    }
    if (len >= 5) {
      update(1, M[input][len - 5] + 1, M[input][len - 4], 0, size - 1, 1);
    }
    ret += query(1, 0, k, 0, size - 1);
  }
  cout << ret << endl;
  return 0;
}
