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 maxn = 5e5 + 10, mod1 = 1e9 + 7, mod2 = 1e9 + 9;
int P1[maxn], P2[maxn], a[maxn], f[maxn], las[maxn], t[maxn], L;
map<pair<int, int>, vector<int> > pos;
int calc(pair<int, int> x) {
  if (!pos[x].size()) return 0;
  int l = 0, r = pos[x].size() - 1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (pos[x][mid] >= L)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return pos[x].size() - r - 1;
}
int main() {
  int n, sum1 = 0, sum2 = 0;
  long long ans = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  P1[0] = P2[0] = 1;
  for (int i = 1; i <= n; i++) {
    P1[i] = P1[i - 1] * 23ll % mod1;
    P2[i] = P2[i - 1] * 23ll % mod2;
  }
  pos[make_pair(0, 0)].push_back(0);
  for (int i = 1; i <= n; i++) {
    las[i] = t[a[i]];
    t[a[i]] = i;
    if (f[a[i]] < 2) {
      f[a[i]]++;
      sum1 = (sum1 + P1[a[i]]) % mod1;
      sum2 = (sum2 + P2[a[i]]) % mod2;
    } else {
      f[a[i]] = 0;
      sum1 = ((sum1 - 2 * P1[a[i]]) % mod1 + mod1) % mod1;
      sum2 = ((sum2 - 2 * P2[a[i]]) % mod2 + mod2) % mod2;
    }
    L = max(L, las[las[las[i]]]);
    ans += calc(make_pair(sum1, sum2));
    pos[make_pair(sum1, sum2)].push_back(i);
  }
  printf("%lld\n", ans);
  return 0;
}
