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 long long INF(0x3f3f3f3f3f3f3f3fll);
const long long inf(0x3f3f3f3f);
const long long N = 5e5 + 10;
long long n, a[N];
struct Seg_Tree {
  long long l, r, lazy, mi, cnt;
} tree[N << 2];
void push_up(long long rt) {
  tree[rt].mi = min(tree[rt << 1].mi, tree[rt << 1 | 1].mi);
  tree[rt].cnt = 0;
  if (tree[rt].mi == tree[rt << 1].mi) tree[rt].cnt += tree[rt << 1].cnt;
  if (tree[rt].mi == tree[rt << 1 | 1].mi)
    tree[rt].cnt += tree[rt << 1 | 1].cnt;
}
void push_down(long long rt) {
  if (tree[rt].lazy) {
    long long x = tree[rt].lazy;
    tree[rt].lazy = 0;
    tree[rt << 1].lazy += x, tree[rt << 1 | 1].lazy += x;
    tree[rt << 1].mi += x, tree[rt << 1 | 1].mi += x;
  }
}
void build(long long l, long long r, long long rt) {
  tree[rt].l = l, tree[rt].r = r;
  tree[rt].cnt = 1;
  tree[rt].lazy = tree[rt].mi = 0;
  if (l == r) return;
  long long mid = l + r >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  push_up(rt);
}
void update_range(long long L, long long R, long long rt, long long val) {
  long long l = tree[rt].l, r = tree[rt].r;
  if (L > R || L > r || R < l) return;
  if (L <= l && r <= R) {
    tree[rt].mi += val;
    tree[rt].lazy += val;
    return;
  }
  push_down(rt);
  long long mid = l + r >> 1;
  if (L <= mid) update_range(L, R, rt << 1, val);
  if (R > mid) update_range(L, R, rt << 1 | 1, val);
  push_up(rt);
}
pair<long long, long long> query_range(long long L, long long R, long long rt) {
  long long l = tree[rt].l, r = tree[rt].r;
  if (L > R || L > r || R < l) return make_pair(inf, 0);
  if (L <= l && r <= R) return make_pair(tree[rt].mi, tree[rt].cnt);
  push_down(rt);
  long long mid = l + r >> 1;
  pair<long long, long long> ans = make_pair(inf, 0);
  if (L <= mid) {
    pair<long long, long long> mi1 = query_range(L, R, rt << 1);
    if (mi1.first < ans.first) ans = mi1;
  }
  if (R > mid) {
    pair<long long, long long> mi2 = query_range(L, R, rt << 1 | 1);
    if (mi2.first == ans.first)
      ans.second += mi2.second;
    else if (mi2.first < ans.first)
      ans = mi2;
  }
  return ans;
}
long long pre[N][5];
signed main() {
  std::ios::sync_with_stdio(false);
  long long n, ans = 0;
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  build(1, n, 1);
  for (long long i = 1; i <= n; i++) {
    update_range(pre[a[i]][1] + 1, i, 1, 1);
    if (pre[a[i]][3] + 1 <= pre[a[i]][2])
      update_range(pre[a[i]][3] + 1, pre[a[i]][2], 1, -1);
    if (pre[a[i]][4] + 1 <= pre[a[i]][3])
      update_range(pre[a[i]][4] + 1, pre[a[i]][3], 1, 1);
    pair<long long, long long> mi = query_range(1, i, 1);
    if (mi.first == 0) ans += mi.second;
    for (long long j = 4; j >= 2; j--) pre[a[i]][j] = pre[a[i]][j - 1];
    pre[a[i]][1] = i;
  }
  cout << ans << '\n';
  return 0;
}
