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;
long long h1[500005], h2[500005], f[500005], pp[500005], b = 5003227,
                                                         b2 = 5000549;
map<long long, long long> m;
vector<long long> v;
string s, q;
queue<int> dq[500005];
int main() {
  long long t, n, a, i, j, k, l, mn = 0, mx = 0, cs = 0;
  h1[0] = 1, h2[0] = 1;
  long long power = 1, power2 = 1;
  for (int j = 1; j <= 500000; j++) {
    h1[j] = (h1[j - 1] + power) % 1000000007;
    power = (power * b) % 1000000007;
  }
  for (int j = 1; j <= 500000; j++) {
    h2[j] = (h2[j - 1] + power2) % 1000000009;
    power2 = (power2 * b2) % 1000000009;
  }
  long long ans = 0, hash1 = 0, hash2 = 0, hashf;
  scanf("%lld", &n);
  m[0] = 1;
  long long sum = 0;
  int lft = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a);
    if (f[a] >= 3) {
      int in = dq[a].front();
      dq[a].pop();
      while (lft < in) {
        m[pp[lft]]--;
        lft++;
      }
    }
    f[a]++;
    dq[a].push(i);
    if (f[a] % 3) {
      hash1 = (hash1 + h1[a]) % 1000000007;
    } else {
      hash1 = (hash1 - (2 * h1[a])) % 1000000007;
      hash1 = (hash1 + 1000000007) % 1000000007;
    }
    if (f[a] % 3) {
      hash2 = (hash2 + h2[a]) % 1000000009;
    } else {
      hash2 = (hash2 - (2 * h2[a])) % 1000000009;
      hash2 = (hash2 + 1000000009) % 1000000009;
    }
    hashf = (hash1 << 32) + hash2;
    ans += m[hashf];
    pp[i] = hashf;
    m[hashf]++;
  }
  printf("%lld\n", ans);
}
