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 N, lazy[1048576];
pair<int, int> st[1048576];
pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
  if (a.first != b.first) return min(a, b);
  return make_pair(a.first, a.second + b.second);
}
void build(int l, int r, int p) {
  if (l == r) {
    st[p] = make_pair(0, 1);
    return;
  }
  int m = (l + r) >> 1;
  build(l, m, 2 * p + 1);
  build(m + 1, r, 2 * p + 2);
  st[p] = merge(st[2 * p + 1], st[2 * p + 2]);
  return;
}
void push(int p) {
  if (lazy[p]) {
    st[p].first += lazy[p];
    if (2 * p + 2 < 1048576) {
      lazy[2 * p + 1] += lazy[p];
      lazy[2 * p + 2] += lazy[p];
    }
    lazy[p] = 0;
  }
  return;
}
void upd(int a, int b, int v, int l, int r, int p) {
  push(p);
  if (a > r || b < l) return;
  if (l >= a && r <= b) {
    st[p].first += v;
    if (l != r) {
      lazy[2 * p + 1] += v;
      lazy[2 * p + 2] += v;
    }
    return;
  }
  int m = (l + r) >> 1;
  upd(a, b, v, l, m, 2 * p + 1);
  upd(a, b, v, m + 1, r, 2 * p + 2);
  st[p] = merge(st[2 * p + 1], st[2 * p + 2]);
  return;
}
int qry(int a, int b, int l, int r, int p) {
  push(p);
  if (a > r || b < l) return 0;
  if (l >= a && r <= b) {
    if (st[p].first) return 0;
    return st[p].second;
  }
  int m = (l + r) >> 1;
  int res = qry(a, b, l, m, 2 * p + 1) + qry(a, b, m + 1, r, 2 * p + 2);
  return res;
}
vector<int> last[500005];
int main() {
  cin >> N;
  build(0, N, 0);
  for (int i = 1; i <= N; ++i) {
    last[i].push_back(0);
  }
  long long ans = 0;
  for (int i = 1; i <= N; ++i) {
    int cur;
    cin >> cur;
    int k = last[cur].size();
    if (k >= 1) {
      upd(last[cur][k - 1], i - 1, 1, 0, N, 0);
    }
    if (k >= 3) {
      upd(last[cur][k - 3], last[cur][k - 2] - 1, -1, 0, N, 0);
    }
    if (k >= 4) {
      upd(last[cur][k - 4], last[cur][k - 3] - 1, 1, 0, N, 0);
    }
    ans += qry(0, i - 1, 0, N, 0);
    last[cur].push_back(i);
  }
  cout << ans << endl;
  return 0;
}
