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>
const int maxn = 5e5 + 10;
int n, a[maxn], last[maxn], vis[maxn], c1[maxn], c3[maxn], p, pre[maxn];
long long ans;
struct data {
  int cnt, min;
};
data NULLDAT() {
  data d;
  d.min = 1e9;
  d.cnt = 0;
  return d;
}
data merge(data a, data b) {
  data c;
  if (a.min < b.min) {
    c.cnt = a.cnt;
  } else if (a.min > b.min) {
    c.cnt = b.cnt;
  } else
    c.cnt = a.cnt + b.cnt;
  c.min = std::min(a.min, b.min);
  return c;
}
struct segmentTree {
  data sum[maxn << 2];
  int tag[maxn << 2];
  void give_tag(int x, int v) {
    tag[x] += v;
    sum[x].min += v;
  }
  void pushdown(int x) {
    tag[x << 1] += tag[x];
    sum[x << 1].min += tag[x];
    tag[x << 1 | 1] += tag[x];
    sum[x << 1 | 1].min += tag[x];
    tag[x] = 0;
  }
  void update(int x) { sum[x] = merge(sum[x << 1], sum[x << 1 | 1]); }
  void build(int l, int r, int rt) {
    if (l == r) {
      sum[rt].cnt = 1;
      sum[rt].min = 0;
      return;
    }
    build(l, (l + r) >> 1, rt << 1);
    build(((l + r) >> 1) + 1, r, rt << 1 | 1);
    update(rt);
  }
  void add(int l, int r, int L, int R, int v, int rt) {
    if (l > R || r < L) return;
    if (l <= L && R <= r) {
      give_tag(rt, v);
      return;
    }
    pushdown(rt);
    add(l, r, L, (L + R) >> 1, v, rt << 1);
    add(l, r, ((L + R) >> 1) + 1, R, v, rt << 1 | 1);
    update(rt);
  }
  data query(int l, int r, int L, int R, int rt) {
    if (l > R || r < L) return NULLDAT();
    if (l <= L && R <= r) return sum[rt];
    pushdown(rt);
    return merge(query(l, r, L, (L + R) >> 1, rt << 1),
                 query(l, r, ((L + R) >> 1) + 1, R, rt << 1 | 1));
  }
  void dfs(int u, int l, int r) {
    if (l == r) {
      printf("%d ", sum[u].min);
      return;
    }
    pushdown(u);
    dfs(u << 1, l, (l + r) >> 1);
    dfs(u << 1 | 1, ((l + r) >> 1) + 1, r);
  }
} sgt;
void update(int x) {
  int u = x;
  int c = a[x];
  if (c1[c]) sgt.add(c3[c] + 1, c1[c], 1, n, -1, 1);
  for (int i = 1; i <= 4; ++i) {
    vis[u]++;
    if (vis[u] == 1) c1[c] = u;
    if (vis[u] == 3) c3[c] = u;
    if (vis[u] == 4) p = std::max(p, u + 1);
    u = pre[u];
    if (!u) break;
  }
  if (c1[c]) sgt.add(c3[c] + 1, c1[c], 1, n, 1, 1);
}
int main() {
  scanf("%d", &n);
  sgt.build(1, n, 1);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    pre[i] = last[a[i]];
    last[a[i]] = i;
    c3[i] = 0;
  }
  p = 1;
  for (int i = 1; i <= n; ++i) {
    update(i);
    data d = sgt.query(p, i, 1, n, 1);
    if (d.min != 0) continue;
    ans += d.cnt;
  }
  printf("%lld", ans);
  return 0;
}
