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;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vc<vc<T>>;
template <class T>
void mkuni(vector<T>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
template <class T>
void print(T x, int suc = 1) {
  cout << x;
  if (suc == 1)
    cout << '\n';
  else
    cout << ' ';
}
template <class T>
void print(const vector<T>& v, int suc = 1) {
  for (int i = 0; i < v.size(); i++)
    print(v[i], i == (int)(v.size()) - 1 ? suc : 2);
}
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
unsigned long long rand_int(unsigned long long l, unsigned long long r) {
  static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<long long>(l, r)(gen);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vc<unsigned long long> hash_v(n + 1);
  for (int i = 1; i <= n; ++i) hash_v[i] = rand_int(1, ULONG_LONG_MAX);
  vc<queue<int>> vpos(n + 1);
  vc<int> cntpre(n + 1, 0);
  vc<unsigned long long> prehash(n + 1, 0);
  map<unsigned long long, int> hashtable;
  hashtable[0]++;
  int start = 0;
  long long ans = 0;
  for (int i = 0, x; i < n; ++i) {
    cin >> x;
    if (vpos[x].size() >= 3) {
      int u = vpos[x].front();
      vpos[x].pop();
      while (start <= u) {
        hashtable[prehash[start]]--;
        ++start;
      }
    }
    int pre = cntpre[x];
    cntpre[x] = (cntpre[x] + 1) % 3;
    prehash[i + 1] = (prehash[i] + (cntpre[x] - pre) * hash_v[x]);
    ans += hashtable[prehash[i + 1]];
    hashtable[prehash[i + 1]]++;
    vpos[x].push(i);
  }
  print(ans);
  return 0;
}
