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;
class segment_tree {
 public:
  struct node {
    int mn = 0;
    int add = 0;
    int cnt = 1;
    void apply(int v) {
      mn += v;
      add += v;
    }
    int zeroCnt() { return (mn == 0) ? cnt : 0; }
  };
  node merge(const node &a, const node &b) const {
    node res;
    res.mn = min(a.mn, b.mn);
    res.cnt = (res.mn == a.mn ? a.cnt : 0) + (res.mn == b.mn ? b.cnt : 0);
    return res;
  }
  void push(int x) {
    tr[x * 2].apply(tr[x].add);
    tr[x * 2 + 1].apply(tr[x].add);
    tr[x].add = 0;
  }
  vector<node> tr;
  int n;
  segment_tree(int _n) : n(_n) {
    int z = 1;
    while (z < n) {
      z <<= 1;
    }
    tr.resize(z * 2);
  }
  template <typename M>
  segment_tree(const vector<M> &v) {
    n = v.size();
    int z = 1;
    while (z < n) {
      z <<= 1;
    }
    tr.resize(z * 2);
    build(1, 0, n - 1, v);
  }
  template <typename M>
  void build(int x, int l, int r, const vector<M> &v) {
    if (l == r) {
      tr[x].apply(v[l]);
    } else {
      int m = (l + r) / 2;
      build(x * 2, l, m, v);
      build(x * 2 + 1, m + 1, r, v);
      tr[x] = merge(tr[x * 2], tr[x * 2 + 1]);
    }
  }
  template <typename... M>
  void update(int x, int cl, int cr, int l, int r, const M &...v) {
    if (l <= cl && cr <= r) {
      tr[x].apply(v...);
    } else {
      push(x);
      int cm = (cl + cr) / 2;
      if (l <= cm) {
        update(x * 2, cl, cm, l, r, v...);
      }
      if (r > cm) {
        update(x * 2 + 1, cm + 1, cr, l, r, v...);
      }
      tr[x] = merge(tr[x * 2], tr[x * 2 + 1]);
    }
  }
  node get(int x, int cl, int cr, int l, int r) {
    if (l <= cl && cr <= r) {
      return tr[x];
    }
    push(x);
    int cm = (cl + cr) / 2;
    node res;
    if (r <= cm) {
      res = get(x * 2, cl, cm, l, r);
    } else if (l > cm) {
      res = get(x * 2 + 1, cm + 1, cr, l, r);
    } else {
      res = merge(get(x * 2, cl, cm, l, r), get(x * 2 + 1, cm + 1, cr, l, r));
    }
    return res;
  }
  template <typename... M>
  void update(int l, int r, const M &...v) {
    assert(0 <= l && l <= r && r <= n - 1);
    update(1, 0, n - 1, l, r, v...);
  }
  node get(int l, int r) {
    assert(0 <= l && l <= r && r <= n - 1);
    return get(1, 0, n - 1, l, r);
  }
};
void foo() {
  int n;
  cin >> n;
  segment_tree st(n);
  long long ans = 0;
  vector<int> cnt(n + 1);
  vector<vector<int>> ind(n + 1, vector<int>(4, -1));
  for (int r = 0; r < n; r++) {
    int v;
    cin >> v;
    cnt[v]++;
    st.update(ind[v][0] + 1, r, 1);
    if (cnt[v] == 3) {
      st.update(ind[v][2] + 1, ind[v][1], -1);
    } else if (cnt[v] >= 4) {
      st.update(ind[v][3] + 1, ind[v][2], 1);
      st.update(ind[v][2] + 1, ind[v][1], -1);
    }
    ind[v][3] = ind[v][2];
    ind[v][2] = ind[v][1];
    ind[v][1] = ind[v][0];
    ind[v][0] = r;
    ans += st.get(0, r).zeroCnt();
  }
  cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  foo();
}
