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 <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << '{';
  string sep;
  for (const auto &x : v) os << sep << x, sep = ", ";
  return os << '}';
}
template <typename T, size_t size>
ostream &operator<<(ostream &os, const array<T, size> &arr) {
  os << '{';
  string sep;
  for (const auto &x : arr) os << sep << x, sep = ", ";
  return os << '}';
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << ' ' << H;
  dbg_out(T...);
}
auto random_address = [] {
  char *p = new char;
  delete p;
  return uint64_t(p);
};
uint64_t splitmix64(uint64_t x) {
  x += 0x9e3779b97f4a7c15;
  x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  return x ^ (x >> 31);
}
const uint64_t FIXED_RANDOM =
    splitmix64(chrono::steady_clock::now().time_since_epoch().count() *
               (random_address() | 1));
template <typename T>
struct array_hash {
  using hash_t = uint64_t;
  int n;
  vector<T> arr;
  hash_t hash;
  array_hash(int _n = 0) { init(_n); }
  array_hash(const vector<T> &_arr) { init(_arr); }
  hash_t get_hash(int index) const {
    assert(0 <= index && index < n);
    return splitmix64(arr[index] ^ splitmix64(index ^ FIXED_RANDOM));
  }
  void compute_hash() {
    hash = 0;
    for (int i = 0; i < n; i++) hash += get_hash(i);
  }
  void init(int _n) {
    n = _n;
    arr.assign(n, 0);
    compute_hash();
  }
  void init(const vector<T> &_arr) {
    arr = _arr;
    n = int(arr.size());
    compute_hash();
  }
  const T &operator[](int index) const { return arr[index]; }
  void modify(int index, const T &value) {
    hash -= get_hash(index);
    arr[index] = value;
    hash += get_hash(index);
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  using hash_t = uint64_t;
  int N;
  cin >> N;
  array_hash<int> freq(N + 1);
  vector<queue<int>> indices(N + 1);
  vector<hash_t> hashes(N + 1);
  unordered_map<hash_t, int> hash_freq;
  hashes[0] = freq.hash;
  hash_freq[hashes[0]]++;
  int64_t answer = 0;
  int start = 0;
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    if (indices[a].size() >= 3) {
      int remove = indices[a].front();
      indices[a].pop();
      while (start <= remove) {
        hash_freq[hashes[start]]--;
        start++;
      }
    }
    freq.modify(a, (freq[a] + 1) % 3);
    hashes[i + 1] = freq.hash;
    answer += hash_freq[freq.hash]++;
    indices[a].push(i);
  }
  cout << answer << '\n';
}
