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>
const int N = 2000005, inf = 5e7;
int n, a[N], lst[N], pre[N], mn[N], cnt[N], tag[N];
long long ans;
inline int Min(const int p, const int q) { return p < q ? p : q; }
inline void B(const int rt, const int l, const int r) {
  tag[rt] = 0, mn[rt] = inf;
  if (l == r) return cnt[rt] = 1, void();
  const int mid = l + r >> 1, ls = rt << 1, rs = ls | 1;
  B(ls, l, mid), B(rs, mid + 1, r), mn[rt] = Min(mn[ls], mn[rs]),
                                    cnt[rt] = (mn[rt] == mn[ls] ? cnt[ls] : 0) +
                                              (mn[rt] == mn[rs] ? cnt[rs] : 0);
}
inline void pd(const int rt) {
  const int ls = rt << 1, rs = ls | 1;
  tag[ls] += tag[rt], tag[rs] += tag[rt], mn[ls] += tag[rt], mn[rs] += tag[rt],
      tag[rt] = 0;
}
inline void upd(const int rt, const int l, const int r, const int u,
                const int v, const int x) {
  if (l >= u && r <= v) return mn[rt] += x, tag[rt] += x, void();
  const int mid = l + r >> 1, ls = rt << 1, rs = ls | 1;
  if (tag[rt]) pd(rt);
  if (u <= mid) upd(ls, l, mid, u, v, x);
  if (v > mid) upd(rs, mid + 1, r, u, v, x);
  mn[rt] = Min(mn[ls], mn[rs]),
  cnt[rt] = (mn[rt] == mn[ls] ? cnt[ls] : 0) + (mn[rt] == mn[rs] ? cnt[rs] : 0);
}
int main() {
  scanf("%d", &n);
  register int i;
  for (i = 1; i <= n; ++i)
    scanf("%d", &a[i]), pre[i] = lst[a[i]], lst[a[i]] = i;
  B(1, 1, n);
  for (i = 1; i <= n; ++i) {
    upd(1, 1, n, i, i, -inf);
    const int p1 = pre[i], p2 = pre[p1], p3 = pre[p2], p4 = pre[p3];
    if (p1) upd(1, 1, n, 1, p1, -1);
    if (p2) upd(1, 1, n, p3 + 1, p2, -1);
    if (p3) upd(1, 1, n, p4 + 1, p3, 1);
    upd(1, 1, n, 1, i, 1);
    if (!mn[1]) ans += cnt[1];
  }
  printf("%lld", ans);
  return 0;
}
