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 M = 5e5 + 15;
const unsigned long long P1 = 15260279, P2 = 8456593;
int a[M], cnt[M], pre[M][6];
unsigned long long h1[M], h2[M], p1[M], p2[M];
map<pair<unsigned long long, unsigned long long>, int> ma;
signed main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  p1[0] = p2[0] = 1;
  for (int i = 1; i <= M - 5; i++) p1[i] = P1 * p1[i - 1];
  for (int i = 1; i <= M - 5; i++) p2[i] = P2 * p2[i - 1];
  unsigned long long nh1 = 0, nh2 = 0;
  int l = 0;
  ma[make_pair(0, 0)] = 1;
  unsigned long long ans = 0;
  for (int i = 1; i <= n; i++) {
    int t = cnt[a[i]] % 3;
    cnt[a[i]]++;
    pre[a[i]][4] = pre[a[i]][3];
    pre[a[i]][3] = pre[a[i]][2];
    pre[a[i]][2] = pre[a[i]][1];
    pre[a[i]][1] = i;
    if (pre[a[i]][4]) {
      while (l < pre[a[i]][4]) ma[make_pair(h1[l], h2[l])]--, l++;
    }
    nh1 = nh1 - p1[a[i]] * t + p1[a[i]] * ((t + 1) % 3);
    nh2 = nh2 - p2[a[i]] * t + p2[a[i]] * ((t + 1) % 3);
    ans += ma[make_pair(nh1, nh2)];
    ma[make_pair(nh1, nh2)]++;
    h1[i] = nh1;
    h2[i] = nh2;
  }
  cout << ans;
  return 0;
}
