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 INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fll;
const long long M = 998244353;
const long long maxn = 1e6 + 107;
const double pi = acos(-1.0);
const double eps = 0.0000000001;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline void pr2(T x, int k = 64) {
  long long i;
  for (i = 0; i < k; i++) fprintf(stderr, "%d", (x >> i) & 1);
  putchar(' ');
}
template <typename T>
inline void add_(T &A, int B, long long MOD = M) {
  A += B;
  (A >= MOD) && (A -= MOD);
}
template <typename T>
inline void mul_(T &A, long long B, long long MOD = M) {
  A = (A * B) % MOD;
}
template <typename T>
inline void mod_(T &A, long long MOD = M) {
  A %= MOD;
  A += MOD;
  A %= MOD;
}
template <typename T>
inline void max_(T &A, T B) {
  (A < B) && (A = B);
}
template <typename T>
inline void min_(T &A, T B) {
  (A > B) && (A = B);
}
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
inline long long powMM(long long a, long long b, long long mod = M) {
  long long ret = 1;
  for (; b; b >>= 1ll, a = a * a % mod)
    if (b & 1) ret = ret * a % mod;
  return ret;
}
int startTime;
void startTimer() { startTime = clock(); }
void printTimer() {
  fprintf(stderr, "/--- Time: %ld milliseconds ---/\n", clock() - startTime);
}
int T[maxn * 4], sum[maxn * 4];
void update(int x, int L, int R) {
  if (T[x])
    sum[x] = 0;
  else {
    if (L == R)
      sum[x] = 1;
    else
      sum[x] = sum[x << 1] + sum[x << 1 | 1];
  }
}
void update(int x, int l, int r, int val, int L, int R) {
  if (l <= L && R <= r) {
    T[x] += val;
    update(x, L, R);
    return;
  }
  int mid = (L + R) / 2;
  if (l <= mid) update(x << 1, l, r, val, L, mid);
  if (mid < r) update(x << 1 | 1, l, r, val, mid + 1, R);
  update(x, L, R);
}
int A[maxn], pre[maxn], id[maxn];
int main() {
  int n, i;
  long long ans = 0;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &A[i]);
  for (i = 1; i <= n; i++) pre[i] = id[A[i]], id[A[i]] = i;
  for (i = 1; i <= n; i++) {
    update(1, i, i, 0, 1, n);
    update(1, pre[i] + 1, i, 1, 1, n);
    int p = pre[pre[i]];
    if (p) update(1, pre[p] + 1, p, -1, 1, n);
    if (pre[p]) update(1, pre[pre[p]] + 1, pre[p], 1, 1, n);
    ans += sum[1];
  }
  printf("%lld\n", ans);
}
