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;
const int N = 5e5 + 5, inf = 1e9;
vector<int> v[N];
int n, a[N];
struct node {
  int v, lz, cnt;
};
node tr[2 * N];
node merge(node a, node b) {
  node c;
  if (a.v == b.v)
    c.v = a.v, c.cnt = a.cnt + b.cnt;
  else if (a.v < b.v)
    c.v = a.v, c.cnt = a.cnt;
  else
    c.v = b.v, c.cnt = b.cnt;
  return c;
}
void apply(int u, int d) { tr[u].v += d, tr[u].lz += d; }
void push(int v, int l, int r) {
  int mid = (l + r) / 2, s = 2 * (mid - l + 1);
  apply(v + 1, tr[v].lz), apply(v + s, tr[v].lz);
}
void build(int v = 1, int l = 1, int r = n) {
  tr[v].lz = 0;
  if (r - l == 0) {
    tr[v].v = 0, tr[v].cnt = 1;
    return;
  }
  int mid = (l + r) / 2, s = 2 * (mid - l + 1);
  build(v + 1, l, mid), build(v + s, mid + 1, r);
  tr[v] = merge(tr[v + 1], tr[v + s]);
}
void udt(int x, int y, int d, int v = 1, int l = 1, int r = n) {
  if (x > r or l > y) return;
  if (l >= x and r <= y) {
    apply(v, d);
    return;
  }
  push(v, l, r);
  int mid = (l + r) / 2, s = 2 * (mid - l + 1);
  udt(x, y, d, v + 1, l, mid), udt(x, y, d, v + s, mid + 1, r);
  tr[v] = merge(tr[v + 1], tr[v + s]);
}
node qry(int x, int y, int v = 1, int l = 1, int r = n) {
  if (y < l or x > r) return {inf, 0};
  if (l >= x and r <= y) return tr[v];
  push(v, l, r);
  int mid = (l + r) / 2, s = 2 * (mid - l + 1);
  node res = {inf, 0};
  res = merge(res, qry(x, y, v + 1, l, mid));
  res = merge(res, qry(x, y, v + s, mid + 1, r));
  return res;
}
int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    v[i].push_back(0);
  }
  build();
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    int sz = v[a[i]].size();
    if (sz >= 1) udt(v[a[i]][sz - 1] + 1, i, 1);
    if (sz >= 4) udt(v[a[i]][sz - 4] + 1, v[a[i]][sz - 3], 1);
    if (sz >= 3) udt(v[a[i]][sz - 3] + 1, v[a[i]][sz - 2], -1);
    v[a[i]].push_back(i);
    node r = qry(1, i);
    if (r.v == 0) ans += r.cnt;
  }
  cout << ans;
}
