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;
int n, l = 1;
map<pair<unsigned long long, unsigned long long>, int> mm;
int app[500010], a[500010];
unsigned long long rnd[3][500010], cnt[500010], ha[500010], ha2[500010];
unsigned long long rnd2[3][500010], ans;
inline unsigned long long rrand() {
  return ((unsigned long long)(rand()) << 31) ^ rand();
}
void init() {
  for (int i = 1; i <= 500000; i++) {
    rnd[0][i] = rrand();
    rnd[1][i] = rrand();
    rnd[2][i] = rnd[0][i] ^ rnd[1][i];
    rnd2[0][i] = rrand();
    rnd2[1][i] = rrand();
    rnd2[2][i] = rnd2[0][i] ^ rnd2[1][i];
  }
}
int main() {
  srand(19260817);
  cin >> n;
  init();
  mm[make_pair(0ull, 0ull)] = 1;
  app[0] = 1;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    ha[i] = ha[i - 1] ^ rnd[cnt[a[i]]][a[i]];
    ha2[i] = ha2[i - 1] ^ rnd2[cnt[a[i]]][a[i]];
    cnt[a[i]] = (cnt[a[i]] + 1) % 3;
    while (app[a[i]] == 3) {
      app[a[l]]--;
      mm[make_pair(ha[l - 1], ha2[l - 1])]--;
      l++;
    }
    app[a[i]]++;
    ans += mm[make_pair(ha[i], ha2[i])];
    mm[make_pair(ha[i], ha2[i])]++;
  }
  cout << ans << '\n';
  return 0;
}
