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;
int A[N], p[N], n;
vector<int> g[N];
int T[N * 4], lazy[N * 4];
void down(int x) {
  if (lazy[x]) {
    lazy[x * 2] += lazy[x];
    T[x * 2] += lazy[x];
    lazy[x * 2 + 1] += lazy[x];
    T[x * 2 + 1] += lazy[x];
    lazy[x] = 0;
  }
}
void change(int root, int l, int r, int L, int R, int v) {
  if (l == L && r == R) {
    lazy[root] += v;
    T[root] += v;
    return;
  }
  down(root);
  int mid = (l + r) / 2;
  if (R <= mid)
    change(root * 2, l, mid, L, R, v);
  else if (L > mid)
    change(root * 2 + 1, mid + 1, r, L, R, v);
  else {
    change(root * 2, l, mid, L, mid, v);
    change(root * 2 + 1, mid + 1, r, mid + 1, R, v);
  }
  T[root] = min(T[root * 2], T[root * 2 + 1]);
}
int qmin(int root, int l, int r, int L, int R) {
  if (l == L && r == R) return T[root];
  down(root);
  int mid = (l + r) / 2;
  if (R <= mid)
    return qmin(root * 2, l, mid, L, R);
  else if (L > mid)
    return qmin(root * 2 + 1, mid + 1, r, L, R);
  else
    return min(qmin(root * 2, l, mid, L, mid),
               qmin(root * 2 + 1, mid + 1, r, mid + 1, R));
}
int find(int x) {
  if (qmin(1, 1, n, 1, x) != 0) return 0;
  int l = 1, r = x, mid;
  while (l + 1 < r) {
    mid = (l + r) / 2;
    if (qmin(1, 1, n, mid, x) == 0)
      l = mid;
    else
      r = mid;
  }
  if (qmin(1, 1, n, r, x) == 0) return r;
  return l;
}
vector<int> G[N];
int ans[N], ma[N], fa[N][25], h[N], val[N];
void dfs(int u, int f) {
  int i, v;
  fa[u][0] = f;
  for (i = 1; i <= 22; i++)
    if (fa[u][i - 1] != -1) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  if (u) h[u] = h[f] + 1;
  for (i = 0; i < G[u].size(); i++) {
    v = G[u][i];
    dfs(v, u);
  }
}
int main() {
  int i, j, a, b, m = 1;
  cin >> n;
  for (i = 1; i <= n; i++) {
    cin >> A[i];
    g[A[i]].push_back(i);
  }
  for (i = 1; i <= n; i++) {
    a = A[i];
    b = p[a]++;
    change(1, 1, n, 1, g[a][b], 1);
    if (b - 3 >= 0) change(1, 1, n, 1, g[a][b - 3], 3);
    if (b - 2 >= 0) change(1, 1, n, 1, g[a][b - 2], -3);
    if (b - 3 >= 0) m = max(m, g[a][b - 3] + 1);
    ma[i] = m;
    val[i] = a = find(i);
    if (a)
      G[a - 1].push_back(i);
    else
      G[0].push_back(i);
  }
  memset(fa, -1, sizeof(fa));
  dfs(0, -1);
  long long sum = 0;
  for (i = 1; i <= n; i++) {
    if (val[i]) {
      a = i;
      for (j = 21; j >= 0; j--)
        if (fa[a][j] >= 1 && val[fa[a][j]] >= ma[i]) a = fa[a][j];
      if (val[a] >= ma[i]) sum += h[i] - h[a] + 1;
    }
  }
  cout << sum << endl;
  return 0;
}
