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;
template <typename T>
bool umax(T& a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
bool umin(T& a, T b) {
  return b < a ? a = b, 1 : 0;
}
const int N = 5e5 + 2;
const long long inf = 1e18;
auto rnd = bind(uniform_int_distribution<long long>(1, 1e9), mt19937(time(0)));
auto rnd1 = bind(uniform_int_distribution<long long>(1, 1e9), mt19937(time(0)));
map<int, int> cl;
map<pair<unsigned long long, unsigned long long>, int> mp;
vector<int> pos[N];
vector<pair<unsigned long long, unsigned long long>> kek[N];
long long vl[N];
long long vl1[N];
int a[N], n;
long long rec(int l, int r) {
  if (l > r) return 0;
  if (l == r) return 0;
  unsigned long long hsh = 0;
  unsigned long long h1 = 0;
  for (int i = l; i <= r; i++) {
    assert(!(int)pos[a[i]].size());
    assert(!(int)kek[i].size());
  }
  cl.clear();
  mp.clear();
  int mid = (l + r) >> 1;
  int to = r;
  for (int i = mid + 1; i <= r; i++) {
    pos[a[i]].push_back(i);
  }
  bool kk = 1;
  for (int i = mid; i >= l; i--) {
    if (cl[a[i]] == 3) kk = 0;
    if (kk) {
      cl[a[i]]++;
      if (cl[a[i]] == 1) {
        hsh += 3ll * vl[a[i]];
        h1 += 3ll * vl1[a[i]];
      }
      hsh -= vl[a[i]];
      h1 -= vl1[a[i]];
      to = min(to, (int)pos[a[i]].size() > 3 - cl[a[i]]
                       ? pos[a[i]][3 - cl[a[i]]] - 1
                       : r);
      if (to ^ mid) kek[to].push_back({hsh, h1});
    }
  }
  long long a1 = 0;
  hsh = 0;
  cl.clear();
  mp.clear();
  h1 = 0;
  bool ok = 1;
  for (int i = mid + 1; i <= r; i++) {
    if (cl[a[i]] == 3) ok = 0;
    if (ok) {
      cl[a[i]]++;
      if (cl[a[i]] == 3) {
        hsh -= 1ll * 2 * vl[a[i]];
        h1 -= 1ll * 2 * vl1[a[i]];
      } else
        hsh += vl[a[i]], h1 += vl1[a[i]];
      mp[{hsh, h1}]++;
    }
    for (auto& z : kek[i]) a1 += mp[z];
    pos[a[i]].clear();
    kek[i].clear();
  }
  return rec(l, mid) + a1 + rec(mid + 1, r);
}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i <= n; i++) vl[i] = rnd();
  for (int i = 0; i <= n; i++) vl1[i] = rnd();
  cout << rec(0, n - 1);
  return 0;
}
