You are given an array a consisting of n integers. We denote the subarray a[l..r] as the array [a_l, a_{l + 1}, ..., a_r] (1 ≤ l ≤ r ≤ n).

A subarray is considered good if every integer that occurs in this subarray occurs there exactly thrice. For example, the array [1, 2, 2, 2, 1, 1, 2, 2, 2] has three good subarrays:

  * a[1..6] = [1, 2, 2, 2, 1, 1]; 
  * a[2..4] = [2, 2, 2]; 
  * a[7..9] = [2, 2, 2]. 



Calculate the number of good subarrays of the given array a.

Input

The first line contains one integer n (1 ≤ n ≤ 5 ⋅ 10^5).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n).

Output

Print one integer — the number of good subarrays of the array a.

Examples

Input


9
1 2 2 2 1 1 2 2 2


Output


3


Input


10
1 2 3 4 1 2 3 1 2 3


Output


0


Input


12
1 2 3 4 3 4 2 1 3 4 2 1


Output


1
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const long long N = 5e5 + 7, M = 1e10;
long long n, a[N], val[N];
queue<long long> q[N];
long long lst[N];
struct Node {
  long long mn, cnt, toadd;
  Node() {}
  Node(long long mn, long long cnt, long long toadd)
      : mn(mn), cnt(cnt), toadd(toadd) {}
};
Node t[4 * N];
Node merge(Node lft, Node rght) {
  Node res;
  res.mn = min(lft.mn, rght.mn);
  res.cnt = 0;
  if (lft.mn == res.mn) res.cnt += lft.cnt;
  if (rght.mn == res.mn) res.cnt += rght.cnt;
  res.toadd = 0;
  return res;
}
void apply(long long v, long long delta) {
  t[v].toadd += delta;
  t[v].mn += delta;
}
void push(long long v) {
  apply(2 * v, t[v].toadd);
  apply(2 * v + 1, t[v].toadd);
  t[v].toadd = 0;
}
void pull(long long v) { t[v] = merge(t[2 * v], t[2 * v + 1]); }
void upd(long long v, long long tl, long long tr, long long l, long long r,
         long long delta) {
  if (tl >= r || tr <= l) return;
  if (tl >= l && tr <= r)
    apply(v, delta);
  else {
    push(v);
    long long tm = (tl + tr) / 2;
    upd(2 * v, tl, tm, l, r, delta);
    upd(2 * v + 1, tm, tr, l, r, delta);
    pull(v);
  }
}
long long query(long long v, long long tl, long long tr, long long l,
                long long r) {
  if (tl >= r || tr <= l) return 0;
  if (tl >= l && tr <= r) return (t[v].mn == 0 ? t[v].cnt : 0);
  push(v);
  long long tm = (tl + tr) / 2;
  return query(2 * v, tl, tm, l, r) + query(2 * v + 1, tm, tr, l, r);
}
void build(long long v, long long l, long long r) {
  if (r - l == 1)
    t[v] = {0, 1, 0};
  else {
    long long m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m, r);
    pull(v);
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (long long i = 0; i < n; ++i) cin >> a[i];
  for (long long i = 1; i <= n; ++i) val[i] = rnd() % M + 1;
  memset(lst, 255, sizeof(lst));
  build(1, 0, n);
  long long mn = n, res = 0;
  for (long long i = n - 1; i >= 0; --i) {
    upd(1, 0, n, i, n, -val[a[i]]);
    q[a[i]].push(i);
    if (q[a[i]].size() == 4) {
      mn = min(mn, q[a[i]].front());
      q[a[i]].pop();
    }
    if (lst[a[i]] != -1) upd(1, 0, n, lst[a[i]], n, -3 * val[a[i]]);
    lst[a[i]] = i;
    upd(1, 0, n, i, n, 3 * val[a[i]]);
    res += query(1, 0, n, i, mn);
  }
  cout << res;
  return 0;
}
