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;
vector<int> a;
vector<pair<int, int>> t;
vector<int> ps;
pair<int, int> merge(const pair<int, int> &a, const pair<int, int> &b) {
  if (a.first != b.first) return min(a, b);
  return make_pair(a.first, a.second + b.second);
}
void push(int v) {
  if (v * 2 + 1 < int(ps.size())) {
    ps[v * 2] += ps[v];
    ps[v * 2 + 1] += ps[v];
  }
  t[v].first += ps[v];
  ps[v] = 0;
}
void build(int v, int l, int r) {
  if (l == r - 1) {
    t[v] = make_pair(0, 1);
    return;
  }
  int m = (l + r) / 2;
  build(v * 2, l, m);
  build(v * 2 + 1, m, r);
  t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
void upd(int v, int l, int r, int L, int R, int val) {
  push(v);
  if (L >= R) return;
  if (l == L && r == R) {
    ps[v] = val;
    push(v);
    return;
  }
  int m = (l + r) / 2;
  upd(v * 2, l, m, L, min(m, R), val);
  upd(v * 2 + 1, m, r, max(m, L), R, val);
  t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
int main() {
  int n;
  scanf("%d", &n);
  a.resize(n);
  for (int i = 0; i < int(n); i++) {
    scanf("%d", &a[i]);
    --a[i];
  }
  t.resize(4 * n);
  ps.resize(4 * n);
  build(1, 0, n);
  vector<vector<int>> pos(n, vector<int>(1, -1));
  long long ans = 0;
  for (int i = 0; i < int(n); i++) {
    int k = pos[a[i]].size();
    if (k >= 1) upd(1, 0, n, pos[a[i]][k - 1] + 1, i + 1, 1);
    if (k >= 3) upd(1, 0, n, pos[a[i]][k - 3] + 1, pos[a[i]][k - 2] + 1, -1);
    if (k >= 4) upd(1, 0, n, pos[a[i]][k - 4] + 1, pos[a[i]][k - 3] + 1, 1);
    pos[a[i]].push_back(i);
    push(1);
    if (t[1].first == 0) ans += t[1].second - (n - i - 1);
  }
  printf("%lld\n", ans);
}
