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;
int n;
int a[500007];
vector<int> v[500007];
int pos[500007];
class Tree {
 public:
  pair<int, int> tr[4 * 500007];
  int lazy[4 * 500007];
  void init(int where, int IL, int IR) {
    tr[where] = {0, IR - IL + 1};
    lazy[where] = 0;
    if (IL == IR) {
      return;
    }
    int mid = (IL + IR) / 2;
    init(2 * where, IL, mid);
    init(2 * where + 1, mid + 1, IR);
  }
  void push_lazy(int where, int IL, int IR) {
    if (lazy[where] == 0) {
      return;
    }
    tr[where].first += lazy[where];
    if (IL != IR) {
      lazy[2 * where] += lazy[where];
      lazy[2 * where + 1] += lazy[where];
    }
    lazy[where] = 0;
  }
  void update(int where, int IL, int IR, int CURL, int CURR, int val) {
    push_lazy(where, IL, IR);
    if (IR < IL || CURL > CURR) {
      return;
    }
    if (CURR < IL || IR < CURL) {
      return;
    }
    if (CURL <= IL && IR <= CURR) {
      lazy[where] += val;
      push_lazy(where, IL, IR);
      return;
    }
    int mid = (IL + IR) / 2;
    update(2 * where, IL, mid, CURL, CURR, val);
    update(2 * where + 1, mid + 1, IR, CURL, CURR, val);
    tr[where].first = min(tr[2 * where].first, tr[2 * where + 1].first);
    tr[where].second =
        (tr[2 * where].first == tr[where].first) * tr[2 * where].second +
        (tr[2 * where + 1].first == tr[where].first) * tr[2 * where + 1].second;
  }
  pair<int, int> query(int where, int IL, int IR, int CURL, int CURR) {
    push_lazy(where, IL, IR);
    if (IR < IL) {
      return {500007, 0};
    }
    if (IR < CURL || CURR < IL) {
      return {500007, 0};
    }
    if (CURL <= IL && IR <= CURR) {
      return tr[where];
    }
    int mid = (IL + IR) / 2;
    pair<int, int> ret1, ret2;
    ret1 = query(2 * where, IL, mid, CURL, CURR);
    ret2 = query(2 * where + 1, mid + 1, IR, CURL, CURR);
    if (ret1.first == ret2.first) {
      ret1.second += ret2.second;
    } else {
      if (ret1.first > ret2.first) {
        ret1 = ret2;
      }
    }
    return ret1;
  }
};
Tree w;
void input() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    v[a[i]].push_back(i);
  }
  for (int i = 0; i < 500007; ++i) {
    pos[i] = v[i].size() - 1;
  }
}
void solve() {
  w.init(1, 1, n);
  long long ans = 0;
  for (int i = n; i >= 1; --i) {
    if (pos[a[i]] + 3 < v[a[i]].size()) {
      int st = v[a[i]][pos[a[i]] + 3];
      int en = n;
      if (pos[a[i]] + 4 < v[a[i]].size()) {
        en = v[a[i]][pos[a[i]] + 4] - 1;
      }
      int nxt = v[a[i]][pos[a[i]] + 1];
      w.update(1, 1, n, nxt, st - 1, -1);
      w.update(1, 1, n, en + 1, n, -1);
    }
    if (pos[a[i]] + 2 < v[a[i]].size()) {
      if (pos[a[i]] + 2 == v[a[i]].size() - 1) {
        int nxt = v[a[i]][pos[a[i]] + 1];
        w.update(1, 1, n, nxt, n, -1);
      }
      int st = v[a[i]][pos[a[i]] + 2];
      int en = n;
      if (pos[a[i]] + 3 < v[a[i]].size()) {
        en = v[a[i]][pos[a[i]] + 3] - 1;
      }
      w.update(1, 1, n, i, st - 1, 1);
      w.update(1, 1, n, en + 1, n, 1);
    } else {
      int nxt = n + 1;
      if (pos[a[i]] + 1 < v[a[i]].size()) {
        nxt = v[a[i]][pos[a[i]] + 1];
      }
      w.update(1, 1, n, i, nxt - 1, 1);
    }
    pair<int, int> aux = w.query(1, 1, n, i, n);
    ans += (aux.first == 0) * aux.second;
    --pos[a[i]];
  }
  printf("%I64d\n", ans);
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  solve();
  return 0;
}
