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>
inline long long ceil_div(long long a, long long b) { return (a + b - 1) / b; }
using namespace std;
inline int qr() {
  int f = 0, fu = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') fu = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    f = (f << 3) + (f << 1) + (c & 15);
    c = getchar();
  }
  return f * fu;
}
const int N = 5e5 + 10, M = 60;
map<vector<int>, int> cnt;
int n;
int val[N][M];
vector<int> pos[N], xr[N];
int main() {
  srand(time(0));
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < M; j++) val[i][j] = rand() % 3;
  long long ans = 0;
  xr[0].resize(M), cnt[xr[0]]++;
  for (int i = 1, j = 0, a; i <= n; i++) {
    scanf("%d", &a);
    pos[a].push_back(i);
    if (pos[a].size() > 3) {
      while (j < pos[a][(int)pos[a].size() - 4]) {
        if (!--cnt[xr[j]]) cnt.erase(xr[j]);
        j++;
      }
    }
    xr[i] = xr[i - 1];
    for (int k = 0; k < M; k++) xr[i][k] = (xr[i][k] + val[a][k]) % 3;
    ans += cnt[xr[i]], ++cnt[xr[i]];
  }
  printf("%lld\n", ans);
  return 0;
}
