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 N = 5e5 + 10;
unsigned long long x[N], y[N], f[N];
int a[N], cnt[N];
queue<int> g[N];
mt19937_64 rng(time(0));
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline int rd() {
  int x = 0, f = 1;
  char ch =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
           ? EOF
           : *p1++);
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  while (isdigit(ch))
    x = x * 10 + (ch ^ 48),
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  return x * f;
}
namespace Hash {
const int hashmod = 999983;
int v[hashmod];
bool vis[hashmod];
unsigned long long h[hashmod];
int &get(unsigned long long S) {
  int i = S % hashmod;
  for (; vis[i] && h[i] != S; i = (i + 1) % hashmod)
    ;
  if (!vis[i]) vis[i] = 1, h[i] = S;
  return v[i];
}
}  // namespace Hash
int main() {
  int n = rd();
  for (int i = 1; i <= n; ++i) {
    a[i] = rd();
    x[i] = rng();
    y[i] = rng();
  }
  unsigned long long now = 0, ans = 0;
  ++Hash::get(now);
  int p = 0;
  for (int i = 1; i <= n; ++i) {
    if (g[a[i]].size() == 3) {
      int t = g[a[i]].front();
      g[a[i]].pop();
      while (p < t) --Hash::get(f[p++]);
    }
    g[a[i]].push(i);
    switch (++cnt[a[i]] % 3) {
      case 1:
        f[i] = now ^= x[a[i]];
        break;
      case 2:
        f[i] = now ^= y[a[i]];
        break;
      case 0:
        f[i] = now ^= x[a[i]] ^ y[a[i]];
        break;
    }
    ans += Hash::get(now)++;
  }
  printf("%lld\n", ans);
}
