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 MX = 5e5 + 5;
using cd = complex<double>;
const double PI = acos(-1);
int sz = 1;
pair<int, int> seg[4 * MX];
int lazy[4 * MX];
pair<int, int> merge(pair<int, int> x, pair<int, int> y) {
  if (y.first == x.first) {
    return {x.first, x.second + y.second};
  } else if (y.first < x.first)
    return y;
  else
    return x;
}
void push(int x, int lx, int rx, int v) {
  seg[x].first += v;
  if (rx - lx != 1) {
    lazy[2 * x + 1] += v;
    lazy[2 * x + 2] += v;
  }
}
void prop(int x, int lx, int rx) {
  push(x, lx, rx, lazy[x]);
  lazy[x] = 0;
}
void build(int x = 0, int lx = 0, int rx = sz) {
  if (rx - lx == 1) {
    seg[x] = {0, 1};
    return;
  }
  int m = (lx + rx) / 2;
  build(2 * x + 1, lx, m), build(2 * x + 2, m, rx);
  seg[x] = merge(seg[2 * x + 1], seg[2 * x + 2]);
}
void upd(int l, int r, int v, int x = 0, int lx = 0, int rx = sz) {
  prop(x, lx, rx);
  if (lx >= r || rx <= l) return;
  if (lx >= l && rx <= r) {
    push(x, lx, rx, v);
    return;
  }
  int m = (lx + rx) / 2;
  upd(l, r, v, 2 * x + 1, lx, m), upd(l, r, v, 2 * x + 2, m, rx);
  seg[x] = merge(seg[2 * x + 1], seg[2 * x + 2]);
}
pair<int, int> query(int l, int r, int x = 0, int lx = 0, int rx = sz) {
  prop(x, lx, rx);
  if (lx >= r || rx <= l) return {10000000, 0};
  if (lx >= l && rx <= r) return seg[x];
  int m = (lx + rx) / 2;
  return merge(query(l, r, 2 * x + 1, lx, m), query(l, r, 2 * x + 2, m, rx));
}
int main() {
  int n;
  cin >> n;
  while (sz < n) sz *= 2;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i], --a[i];
  vector<array<int, 4>> lst(n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 4; j++) lst[i][j] = -1;
  }
  long long ans = 0LL;
  build();
  for (int i = 0; i < n; i++) {
    if (lst[a[i]][0] != -1) upd(lst[a[i]][2] + 1, lst[a[i]][0] + 1, -1);
    if (lst[a[i]][3] != -1) upd(0, lst[a[i]][3] + 1, -1);
    for (int j = 3; j >= 1; j--) lst[a[i]][j] = lst[a[i]][j - 1];
    lst[a[i]][0] = i;
    if (lst[a[i]][0] != -1) upd(lst[a[i]][2] + 1, lst[a[i]][0] + 1, 1);
    if (lst[a[i]][3] != -1) upd(0, lst[a[i]][3] + 1, 1);
    pair<int, int> curr = query(0, i + 1);
    if (curr.first == 0) ans += curr.second;
  }
  cout << ans << "\n";
}
