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;
inline int add(int _a, int _b, int md) {
  if (_a < 0) {
    _a += md;
  }
  if (_b < 0) {
    _b += md;
  }
  if (_a + _b >= md) {
    return _a + _b - md;
  }
  return _a + _b;
}
inline int mul(int _a, int _b, int md) {
  if (_a < 0) {
    _a += md;
  }
  if (_b < 0) {
    _b += md;
  }
  return ((long long int)((long long int)_a * (long long int)_b)) % md;
}
const int N = 5e5;
int mod[] = {1000000007, 1000000007 + 2};
int base[] = {31, 47}, pwr[2][N + 5];
int n, ara[N + 5], fqj[N + 5], fqi[N + 5], fq[N + 5];
map<long long int, int> mp;
long long int get_key(int a, int b) {
  return ((long long int)a << 31ll) | (long long int)b;
}
int main() {
  int i, j, k;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &ara[i]);
  for (i = 0; i < 2; ++i) {
    for (j = 1, pwr[i][0] = 1; j <= n; ++j) {
      pwr[i][j] = mul(pwr[i][j - 1], base[i], mod[i]);
    }
  }
  int cnt[4];
  memset(cnt, 0, sizeof(cnt));
  int hashi[2], hashj[2];
  memset(hashi, 0, sizeof(hashi)), memset(hashj, 0, sizeof(hashj));
  cnt[0] = n;
  long long int ans = 0;
  for (i = j = 0; i < n; ++i) {
    for (; j < n; ++j) {
      int x = fq[ara[j]];
      if (x + 1 == 4) break;
      cnt[x]--, cnt[x + 1]++;
      int a = fqj[ara[j]] % 3;
      int b = (a + 1) % 3;
      for (k = 0; k < 2; ++k) {
        hashj[k] = add(hashj[k], -mul(a, pwr[k][ara[j]], mod[k]), mod[k]);
        hashj[k] = add(hashj[k], mul(b, pwr[k][ara[j]], mod[k]), mod[k]);
      }
      fqj[ara[j]]++, fq[ara[j]]++;
      mp[get_key(hashj[0], hashj[1])]++;
    }
    ans += mp[get_key(hashi[0], hashi[1])];
    int x = fq[ara[i]];
    cnt[x]--, cnt[x - 1]++;
    int a = fqi[ara[i]] % 3;
    int b = (a + 1) % 3;
    for (k = 0; k < 2; ++k) {
      hashi[k] = add(hashi[k], -mul(a, pwr[k][ara[i]], mod[k]), mod[k]);
      hashi[k] = add(hashi[k], mul(b, pwr[k][ara[i]], mod[k]), mod[k]);
    }
    fqi[ara[i]]++, fq[ara[i]]--;
    mp[get_key(hashi[0], hashi[1])]--;
  }
  printf("%lld", ans), puts("");
  return 0;
}
