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 = 500001;
namespace SEG {
int st[1 << 20], tg[1 << 20];
void push_up(int p, int lb, int rb) {
  if (tg[p])
    st[p] = 0;
  else if (lb + 1 == rb)
    st[p] = 1;
  else
    st[p] = st[p << 1] + st[p << 1 | 1];
}
void build(int p, int lb, int rb) {
  if (lb + 1 != rb) {
    int mid = (lb + rb) >> 1;
    build(p << 1, lb, mid);
    build(p << 1 | 1, mid, rb);
  }
  push_up(p, lb, rb);
}
void modify(int l, int r, int v, int p, int lb, int rb) {
  if (l <= lb && rb <= r)
    tg[p] += v;
  else {
    int mid = (lb + rb) >> 1;
    if (l < mid) modify(l, r, v, p << 1, lb, mid);
    if (r > mid) modify(l, r, v, p << 1 | 1, mid, rb);
  }
  push_up(p, lb, rb);
}
int query(int l, int r, int c, int p, int lb, int rb) {
  if (l <= lb && rb <= r)
    return c ? 0 : st[p];
  else {
    int mid = (lb + rb) >> 1;
    int sum = 0;
    if (l < mid) sum += query(l, r, c + tg[p], p << 1, lb, mid);
    if (r > mid) sum += query(l, r, c + tg[p], p << 1 | 1, mid, rb);
    return sum;
  }
}
}  // namespace SEG
int p[4][N];
int main(void) {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) p[1][i] = p[2][i] = p[3][i] = -1, p[0][i] = 0;
  SEG::build(1, 1, n + 1);
  long long sum = 0;
  for (int i = 1; i <= n; ++i) {
    int a;
    scanf("%d", &a);
    SEG::modify(p[0][a] + 1, i + 1, 1, 1, 1, n + 1);
    if (p[3][a] != -1) SEG::modify(p[3][a] + 1, p[2][a] + 1, 1, 1, 1, n + 1);
    if (p[2][a] != -1) SEG::modify(p[2][a] + 1, p[1][a] + 1, -1, 1, 1, n + 1);
    int res = SEG::query(1, i + 1, 0, 1, 1, n + 1);
    sum += res;
    p[3][a] = p[2][a];
    p[2][a] = p[1][a];
    p[1][a] = p[0][a];
    p[0][a] = i;
  }
  printf("%lld\n", sum);
  return 0;
}
