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;
int tag[500005 << 2], minn[500005 << 2], num[500005 << 2];
void push_tag(int p, int v) {
  minn[p] += v;
  tag[p] += v;
}
void push_up(int p) {
  minn[p] = min(minn[p << 1], minn[p << 1 | 1]);
  num[p] = 0;
  if (minn[p << 1] == minn[p]) num[p] += num[p << 1];
  if (minn[p << 1 | 1] == minn[p]) num[p] += num[p << 1 | 1];
}
void push_down(int p) {
  if (tag[p]) {
    push_tag(p << 1, tag[p]);
    push_tag(p << 1 | 1, tag[p]);
    tag[p] = 0;
  }
}
void build(int p, int l, int r) {
  if (l == r) {
    num[p] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
  push_up(p);
}
void modify(int p, int l, int r, int ql, int qr, int v) {
  if (ql <= l && qr >= r) {
    push_tag(p, v);
    return;
  }
  push_down(p);
  int mid = (l + r) >> 1;
  if (ql <= mid) modify(p << 1, l, mid, ql, qr, v);
  if (qr > mid) modify(p << 1 | 1, mid + 1, r, ql, qr, v);
  push_up(p);
}
pair<int, int> query(int p, int l, int r, int ql, int qr) {
  if (ql <= l && qr >= r) return make_pair(minn[p], num[p]);
  int mid = (l + r) >> 1;
  push_down(p);
  pair<int, int> res = make_pair(0x3f3f3f3f, 0);
  if (ql <= mid) {
    pair<int, int> tmp = query(p << 1, l, mid, ql, qr);
    if (tmp.first == res.first) res.second += tmp.second;
    if (tmp.first < res.first) {
      res.first = tmp.first;
      res.second = tmp.second;
    }
  }
  if (qr > mid) {
    pair<int, int> tmp = query(p << 1 | 1, mid + 1, r, ql, qr);
    if (tmp.first == res.first) res.second += tmp.second;
    if (tmp.first < res.first) {
      res.first = tmp.first;
      res.second = tmp.second;
    }
  }
  return res;
}
int n, a[500005], pos[500005], pre[500005];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) {
    pre[i] = pos[a[i]];
    pos[a[i]] = i;
  }
  build(1, 1, n);
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    modify(1, 1, n, 1, i, 1);
    if (pre[pre[i]]) modify(1, 1, n, pre[pre[pre[i]]] + 1, pre[pre[i]], -3);
    pair<int, int> tmp = query(1, 1, n, 1, i);
    if (tmp.first == 0) ans += tmp.second;
  }
  printf("%lld", ans);
  return 0;
}
