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 long long int inf = (long long int)1e9;
long long int n;
long long int power[61] = {0};
long long int N;
vector<long long int> good;
vector<pair<pair<long long int, long long int>,
            pair<long long int, long long int>>>
    segtree;
vector<pair<long long int, pair<long long int, long long int>>> lazy;
void fill(long long int v) {
  if (2 * v + 1 < power[N + 1] - 1) {
    fill(2 * v + 1);
    fill(2 * v + 2);
    segtree[v].first.first =
        min(segtree[2 * v + 1].first.first, segtree[2 * v + 2].first.first);
    if (segtree[2 * v + 1].first.first == segtree[2 * v + 2].first.first) {
      segtree[v].first.second =
          segtree[2 * v + 1].first.second + segtree[2 * v + 2].first.second;
    } else if (segtree[2 * v + 1].first.first <
               segtree[2 * v + 2].first.first) {
      segtree[v].first.second = segtree[2 * v + 1].first.second;
    } else {
      segtree[v].first.second = segtree[2 * v + 2].first.second;
    }
    segtree[v].second.first = segtree[2 * v + 1].second.first;
    lazy[v].second.first = lazy[2 * v + 1].second.first;
    segtree[v].second.second = segtree[2 * v + 2].second.second;
    lazy[v].second.second = lazy[2 * v + 2].second.second;
  } else {
    return;
  }
}
void update(long long int l, long long int r, long long int val,
            long long int curr) {
  if (lazy[curr].first != 0) {
    segtree[curr].first.first += lazy[curr].first;
    if (segtree[curr].second.first != segtree[curr].second.second) {
      lazy[2 * curr + 1].first += lazy[curr].first;
      lazy[2 * curr + 2].first += lazy[curr].first;
    }
    lazy[curr].first = 0;
  }
  if (segtree[curr].second.second < l || segtree[curr].second.first > r) {
    return;
  }
  if ((segtree[curr].second.first >= l) && (segtree[curr].second.second <= r)) {
    segtree[curr].first.first += val;
    if (segtree[curr].second.first != segtree[curr].second.second) {
      lazy[2 * curr + 1].first += val;
      lazy[2 * curr + 2].first += val;
    }
    return;
  }
  update(l, r, val, 2 * curr + 1);
  update(l, r, val, 2 * curr + 2);
  segtree[curr].first.first =
      min(segtree[2 * curr + 1].first.first, segtree[2 * curr + 2].first.first);
  if (segtree[2 * curr + 1].first.first == segtree[2 * curr + 2].first.first) {
    segtree[curr].first.second =
        segtree[2 * curr + 1].first.second + segtree[2 * curr + 2].first.second;
  } else if (segtree[2 * curr + 1].first.first <
             segtree[2 * curr + 2].first.first) {
    segtree[curr].first.second = segtree[2 * curr + 1].first.second;
  } else {
    segtree[curr].first.second = segtree[2 * curr + 2].first.second;
  }
  return;
}
pair<long long int, long long int> mn(long long int l, long long int r,
                                      long long int v) {
  if (lazy[v].first != 0) {
    segtree[v].first.first += lazy[v].first;
    if (segtree[v].second.first != segtree[v].second.second) {
      lazy[2 * v + 1].first += lazy[v].first;
      lazy[2 * v + 2].first += lazy[v].first;
    }
    lazy[v].first = 0;
  }
  if (segtree[v].second.first >= l && segtree[v].second.second <= r) {
    return segtree[v].first;
  } else if (segtree[v].second.second < l || segtree[v].second.first > r) {
    return {inf, 0};
  } else {
    pair<long long int, long long int> p1 = mn(l, r, 2 * v + 1);
    pair<long long int, long long int> p2 = mn(l, r, 2 * v + 2);
    if (p1.first == p2.first) {
      return {p1.first, p1.second + p2.second};
    } else if (p1.first < p2.first) {
      return p1;
    } else {
      return p2;
    }
  }
}
void solve() {
  vector<long long int> v(n);
  vector<vector<long long int>> pos(n + 1);
  for (long long int j = 0; j < n; j++) {
    cin >> v[j];
  }
  long long int ans = 0;
  for (long long int j = 0; j < n; j++) {
    pos[v[j]].push_back(j);
    long long int k = (long long int)pos[v[j]].size();
    if (k < 3) {
      update(0, j, 1, 0);
    } else if (k == 3) {
      update(0, pos[v[j]][k - 3], -2, 0);
      update(pos[v[j]][k - 3] + 1, j, 1, 0);
    } else {
      update(pos[v[j]][k - 4] + 1, pos[v[j]][k - 3], -2, 0);
      update(pos[v[j]][k - 3] + 1, j, 1, 0);
      update(0, pos[v[j]][k - 4], 1, 0);
    }
    pair<long long int, long long int> p = mn(0, j, 0);
    if (p.first == 0) {
      ans += p.second;
    }
  }
  cout << ans << "\n";
  return;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t;
  t = 1;
  power[0] = 1;
  for (long long int j = 1; j <= 60; j++) power[j] = power[j - 1] * 2;
  cin >> n;
  good.resize(n, 0);
  for (long long int j = 0; j <= 60; j++) {
    if (power[j] >= n) {
      N = j;
      break;
    }
  }
  segtree.resize(power[N + 1] - 1);
  lazy.resize(power[N + 1] - 1);
  for (long long int j = n; j < power[N]; j++) {
    good.push_back(inf);
  }
  for (long long int j = power[N] - 1; j < power[N + 1] - 1; j++) {
    segtree[j].first = {good[j - (power[N] - 1)], 1};
    lazy[j].first = 0;
    segtree[j].second.first = j - power[N] + 1;
    lazy[j].second.first = j - power[N] + 1;
    segtree[j].second.second = j - power[N] + 1;
    lazy[j].second.second = j - power[N] + 1;
  }
  fill(0);
  while (t--) {
    solve();
  }
  return 0;
}
