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>
#pragma GCC optimize(2)
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 500000 + 20;
int n;
vector<int> c[MAXN];
const int N = 1 << 19;
struct segtree {
  pair<int, int> tree[N + N];
  int lazy_tag[N + N];
  pair<int, int> merge(pair<int, int> A, pair<int, int> B) {
    pair<int, int> rest = make_pair(0, 0);
    rest.first = max(A.first, B.first);
    if (A.first == rest.first) {
      rest.second += A.second;
    }
    if (B.first == rest.first) {
      rest.second += B.second;
    }
    return rest;
  }
  void mian() {
    for (int i = N; i <= N + N - 1; ++i) tree[i] = make_pair(0, 1);
    for (int i = 1; i <= N - 1; ++i)
      tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
  }
  void push_down(int index) {
    tree[index].first += lazy_tag[index];
    if (index < N) {
      lazy_tag[index << 1] += lazy_tag[index];
      lazy_tag[index << 1 | 1] += lazy_tag[index];
    }
    lazy_tag[index] = 0;
  }
  void modify(int a, int b, int val, int now = 1, int l = 1, int r = N + 1) {
    push_down(now);
    if (r <= a || l >= b) {
      return;
    }
    if (r <= b && l >= a) {
      lazy_tag[now] += val;
      push_down(now);
      return;
    }
    int mid = (l + r) >> 1;
    modify(a, b, val, now << 1, l, mid);
    modify(a, b, val, now << 1 | 1, mid, r);
    tree[now] = merge(tree[now << 1], tree[now << 1 | 1]);
  }
  pair<int, int> query(int a, int b, int now = 1, int l = 1, int r = N + 1) {
    push_down(now);
    if (r <= a || l >= b) {
      return make_pair(0, 0);
    }
    if (r <= b && l >= a) {
      return tree[now];
    }
    int mid = (l + r) >> 1;
    return merge(query(a, b, now << 1, l, mid),
                 query(a, b, now << 1 | 1, mid, r));
  }
} t;
int a[MAXN];
void paint(int l, int r, int ll, int cal) {
  if (l) {
    ll++;
    if (l >= ll) t.modify(ll, l + 1, cal);
  }
  if (r != n) {
    t.modify(r + 1, n + 1, cal);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  if (n < 3) {
    cout << 0 << endl;
    return 0;
  }
  t.mian();
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j < 5; ++j) c[i].push_back(0);
  for (int i = 1; i <= n; ++i) {
    c[a[i]].push_back(i);
  }
  for (int i = 1; i <= n; ++i) {
    int l, r;
    r = c[i].back();
    l = c[i][c[i].size() - 3];
    int ll = c[i][c[i].size() - 4];
    paint(l, r, ll, 1);
  }
  long long rest = 0;
  for (int i = n; i >= 1; --i) {
    if (i != n) {
      int col = a[i + 1];
      int l, r, ll;
      r = c[col].back();
      l = c[col][c[col].size() - 3];
      ll = c[col][c[col].size() - 4];
      paint(l, r, ll, -1);
      c[col].pop_back();
      r = c[col].back();
      l = c[col][c[col].size() - 3];
      ll = c[col][c[col].size() - 4];
      paint(l, r, ll, 1);
    }
    pair<int, int> q = t.query(1, i);
    if (q.first == n) rest += q.second;
  }
  cout << rest << endl;
  return 0;
}
