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;
template <class T, class T1>
int chkmin(T &x, const T1 &y) {
  return x > y ? x = y, 1 : 0;
}
template <class T, class T1>
int chkmax(T &x, const T1 &y) {
  return x < y ? x = y, 1 : 0;
}
const int MAXN = (1 << 20);
struct count_max_segment_tree {
  struct node {
    int mx, cnt, lazy;
    node() { mx = -(int)1e9, cnt = 0, lazy = 0; }
    node(int v) {
      mx = v;
      cnt = 1;
      lazy = 0;
    }
  };
  node merge(node a, node b) {
    node ret = node();
    ret.mx = max(a.mx, b.mx);
    ret.cnt = 0;
    if (ret.mx == a.mx) ret.cnt += a.cnt;
    if (ret.mx == b.mx) ret.cnt += b.cnt;
    return ret;
  }
  node tr[MAXN << 2];
  void push(int l, int r, int idx) {
    if (tr[idx].lazy) {
      tr[idx].mx += tr[idx].lazy;
      if (l != r) {
        tr[2 * idx + 1].lazy += tr[idx].lazy;
        tr[2 * idx + 2].lazy += tr[idx].lazy;
      }
      tr[idx].lazy = 0;
    }
  }
  void init(int l, int r, int idx) {
    if (l == r) {
      tr[idx] = node(-l);
      return;
    }
    int mid = (l + r) >> 1;
    init(l, mid, 2 * idx + 1);
    init(mid + 1, r, 2 * idx + 2);
    tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  }
  void add(int ql, int qr, int v, int l, int r, int idx) {
    push(l, r, idx);
    if (qr < l || ql > r) {
      return;
    }
    if (ql <= l && r <= qr) {
      tr[idx].lazy += v;
      push(l, r, idx);
      return;
    }
    int mid = (l + r) >> 1;
    add(ql, qr, v, l, mid, 2 * idx + 1);
    add(ql, qr, v, mid + 1, r, 2 * idx + 2);
    tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  }
  node query(int ql, int qr, int l, int r, int idx) {
    push(l, r, idx);
    if (qr < l || ql > r) {
      return node();
    }
    if (ql <= l && r <= qr) {
      return tr[idx];
    }
    int mid = (l + r) >> 1;
    return merge(query(ql, qr, l, mid, 2 * idx + 1),
                 query(ql, qr, mid + 1, r, 2 * idx + 2));
  }
  void walk(int l, int r, int idx) {
    push(l, r, idx);
    if (l == r) {
      cout << l << ": "
           << "{" << tr[idx].mx << " " << tr[idx].cnt
           << " lazy=" << tr[idx].lazy << "}"
           << " ";
      return;
    }
    int mid = (l + r) >> 1;
    walk(l, mid, 2 * idx + 1);
    walk(mid + 1, r, 2 * idx + 2);
    tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  }
};
int n;
int a[MAXN];
void read() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
}
vector<int> last[MAXN];
count_max_segment_tree mt;
void solve() {
  for (int i = 1; i <= n; i++) {
    last[i].push_back(-1);
    last[i].push_back(-1);
    last[i].push_back(-1);
  }
  mt.init(0, n - 1, 0);
  int l_bound = -1;
  int64_t ans = 0;
  for (int i = 0; i < n; i++) {
    last[a[i]].push_back(i);
    chkmax(l_bound, last[a[i]][0]);
    last[a[i]].erase(last[a[i]].begin());
    mt.add(last[a[i]][1] + 1, i, -3, 0, n - 1, 0);
    auto candidates = mt.query(l_bound + 1, i, 0, n - 1, 0);
    if (candidates.mx + i + 1 == 0) {
      ans += candidates.cnt;
    }
  }
  cout << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  read();
  solve();
  return 0;
}
