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 nax = 5e5 + 5;
int a[nax];
int n;
const int mod = 1e9 + 7;
long long int get() {
  return ((long long int)rand() << 45) + ((long long int)rand() << 30) +
         (rand() << 16) + rand();
}
long long int hasz[nax][3];
long long int p[nax];
int cnt[nax];
map<int, int> xd;
const int roz = (1 << 20);
int tree[roz];
void add(int lo, int hi, int u, int a, int b, int val) {
  if (lo == a && b == hi) {
    tree[u] += val;
    return;
  }
  if (b <= a) return;
  int mid = (lo + hi) / 2;
  add(lo, mid, u * 2, a, min(b, mid), val);
  add(mid, hi, u * 2 + 1, max(a, mid), b, val);
}
int ask(int pos) {
  int ans = 0;
  pos += roz / 2;
  while (pos >= 1) {
    ans += tree[pos];
    pos /= 2;
  }
  return ans;
}
map<int, vector<int> > mapka;
map<int, vector<long long int> > hasze;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 3; j++) hasz[i][j] = get();
  }
  for (int i = 1; i <= n; i++) {
    cnt[a[i]]++;
    long long int akt = hasz[a[i]][cnt[a[i]] % 3];
    long long int pop = hasz[a[i]][(cnt[a[i]] + 2) % 3];
    p[i] = p[i - 1] ^ (akt ^ pop);
  }
  for (int i = 1; i <= n; i++) {
    mapka[i].push_back(0);
  }
  long long int ans = 0;
  hasze[0].push_back(0);
  for (int i = 1; i <= n; i++) {
    int cur = a[i];
    int pop = mapka[cur].back();
    add(0, roz / 2, 1, pop + 1, i + 1, 1);
    mapka[cur].push_back(i);
    int hasz = p[i];
    int lo = 0;
    int hi = hasze[hasz].size() - 1;
    if (hi < lo) {
      hasze[hasz].push_back(i);
      continue;
    }
    int ost = hasze[hasz].back();
    int len = i - ost;
    int cnt = ask(ost + 1);
    if (cnt * 3 != len) {
      hasze[hasz].push_back(i);
      continue;
    }
    while (lo + 1 < hi) {
      int mid = (lo + hi) / 2;
      int v = hasze[hasz][mid];
      int len = i - v;
      int cnt = ask(v + 1);
      if (cnt * 3 == len)
        hi = mid;
      else
        lo = mid;
    }
    int ok = hi;
    int v = hasze[hasz][lo];
    len = i - v;
    cnt = ask(v + 1);
    if (cnt * 3 == len) ok = lo;
    ans += hasze[hasz].size() - ok;
    hasze[hasz].push_back(i);
  }
  cout << ans;
  return 0;
}
