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 N = 1e6;
int cnt[4 * N + 8], sm[4 * N + 8], dsm[4 * N + 8];
void upd(int node, int lo, int hi, int lt, int rt, int vl) {
  if (lo > rt || hi < lt) return;
  if (lo >= lt && hi <= rt) {
    cnt[node] += vl;
    if (cnt[node])
      sm[node] = hi - lo + 1;
    else
      sm[node] = dsm[node];
    return;
  }
  int md = (lo + hi) / 2;
  upd(node * 2, lo, md, lt, rt, vl), upd(node * 2 + 1, md + 1, hi, lt, rt, vl);
  dsm[node] = sm[node * 2] + sm[node * 2 + 1];
  if (cnt[node])
    sm[node] = hi - lo + 1;
  else
    sm[node] = dsm[node];
}
int a[N + 2];
vector<int> po[N + 2];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) po[i].push_back(n + 1);
  long long ans = 0;
  for (int i = n; i >= 1; i--) {
    int sz = po[a[i]].size();
    upd(1, 1, n, i, po[a[i]][sz - 1] - 1, 1);
    if (sz - 3 >= 0) upd(1, 1, n, po[a[i]][sz - 2], po[a[i]][sz - 3] - 1, -1);
    if (sz - 4 >= 0) upd(1, 1, n, po[a[i]][sz - 3], po[a[i]][sz - 4] - 1, 1);
    ans += n - i + 1 - sm[1];
    po[a[i]].push_back(i);
  }
  cout << ans << endl;
  return 0;
}
