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 maxi = 1e6 + 10;
const long long mo = 1e18;
mt19937 rng(time(0));
int n;
int a[maxi];
long long p[maxi];
int cnt[maxi];
long long solve(int l, int r) {
  if (r < l) return 0;
  set<int> active;
  int mid = (l + r) / 2;
  long long ans = 0;
  map<long long, int> mp;
  map<int, int> poz;
  long long curSum = 0;
  stack<long long> v;
  for (int i = mid; i >= l; i--) {
    if (active.find(a[i]) == active.end()) {
      cnt[a[i]] = 1;
      curSum += p[a[i]];
      active.insert(a[i]);
      poz[a[i]] = i;
    } else {
      cnt[a[i]]++;
      if (cnt[a[i]] == 4) break;
      if (cnt[a[i]] == 3)
        curSum -= 2 * p[a[i]];
      else
        curSum += p[a[i]];
    }
    v.push(curSum);
    mp[curSum]++;
  }
  active.clear();
  int right = l - 1;
  ans += mp[0];
  curSum = 0;
  for (int i = mid + 1; i <= r; i++)
    if (active.find(a[i]) == active.end()) {
      cnt[a[i]] = 1;
      curSum += 2 * p[a[i]];
      active.insert(a[i]);
      if (mp.count(curSum)) ans += mp[curSum];
    } else {
      cnt[a[i]]++;
      if (cnt[a[i]] == 4) break;
      if (cnt[a[i]] == 3) {
        right = max(right, poz[a[i]]);
        while (mid - right < v.size()) {
          mp[v.top()]--;
          v.pop();
        }
      }
      curSum -= p[a[i]];
      if (mp.count(curSum)) ans += mp[curSum];
    }
  ans += solve(l, mid - 1) + solve(mid + 1, r);
  return ans;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) p[i] = rng() * (1ll << 31) + rng();
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  cout << solve(1, n);
}
