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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long int getRand(long long int l, long long int r) {
  uniform_int_distribution<long long int> uid(l, r);
  return uid(rng);
}
const long long int N = 1e5 + 5, inf = 1e18;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int n;
  cin >> n;
  long long int ary[n], rnd[n], hsh[n];
  vector<long long int> pre[n];
  for (long long int i = 0; i < n; ++i) {
    cin >> ary[i];
    ary[i]--;
    rnd[i] = getRand(0, 1e18);
  }
  map<long long int, long long int> M;
  M[0] = 1;
  long long int cur = 0, req = 0, del = 0, ans = 0, f = 0;
  long long int c = 0;
  for (long long int i = 0; i < n; ++i) {
    cur -= (((long long int)((pre[ary[i]]).size())) % 3) * rnd[ary[i]];
    if (((long long int)((pre[ary[i]]).size())) >= 3) {
      long long int x =
          pre[ary[i]][((long long int)((pre[ary[i]]).size())) - 3];
      if (f == 0) M[0]--;
      f = 1;
      while (del < x) {
        M[hsh[del]]--;
        del++;
      }
    }
    pre[ary[i]].push_back(i);
    cur += (((long long int)((pre[ary[i]]).size())) % 3) * rnd[ary[i]];
    ans += M[cur];
    M[cur]++;
    hsh[i] = cur;
  }
  cout << ans << "\n";
  return 0;
}
