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 inf = 1 << 30;
const long long Inf = 1ll << 60ll;
namespace io {
char buf[(1 << 23)], *p1 = buf, *p2 = buf, c;
int f;
template <typename T>
T read() {
  T x = 0;
  f = 0;
  c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 23), stdin), p1 == p2)
           ? EOF
           : *p1++);
  while (!isdigit(c))
    (c == '-') && (f = 1),
        c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 23), stdin),
                          p1 == p2)
                 ? EOF
                 : *p1++);
  while (isdigit(c))
    x = x * 10 + (c & 15),
    c = (p1 == p2 &&
                 (p2 = (p1 = buf) + fread(buf, 1, (1 << 23), stdin), p1 == p2)
             ? EOF
             : *p1++);
  return f ? -x : x;
}
}  // namespace io
const int N = 500005;
mt19937 engine(19260817);
int n, a[N], lst[N], p[N], cnt[N];
unsigned long long base[N], ha[N];
map<unsigned long long, int> mp;
long long ans;
int main() {
  n = io::read<int>();
  for (int i = 1; i <= n; ++i) a[i] = io::read<int>();
  for (int i = 1; i <= n; ++i) base[i] = engine() * (1ull << 32) + engine();
  for (int i = 1; i <= n; ++i) {
    cnt[a[i]]++;
    if (cnt[a[i]] >= 3) cnt[a[i]] -= 3;
    if (cnt[a[i]])
      ha[i] = ha[i - 1] + base[a[i]];
    else
      ha[i] = ha[i - 1] - 2 * base[a[i]];
  }
  for (int i = 1; i <= n; ++i) {
    lst[i] = p[a[i]];
    p[a[i]] = i;
  }
  mp[0] = 1;
  int cur = -1;
  for (int i = 1; i <= n; ++i) {
    int pos = lst[lst[lst[i]]] - 1;
    while (cur < pos) {
      ++cur;
      mp[ha[cur]]--;
    }
    ans += mp[ha[i]];
    mp[ha[i]]++;
  }
  printf("%lld\n", ans);
  return 0;
}
