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;
const long long INF = 1LL << 60;
struct Datum {
  Datum(long long v = INF, long long c = 1) : val(v), cnt(c) {}
  Datum operator+(const Datum& other) const {
    Datum res(other);
    if (res.val > val) {
      res.val = val;
      res.cnt = cnt;
    } else if (res.val == val) {
      res.cnt += cnt;
    }
    return res;
  }
  Datum operator+(long long x) const {
    Datum res(*this);
    res.val += x;
    return res;
  }
  Datum& operator+=(long long x) {
    val += x;
    return *this;
  }
  long long val;
  long long cnt;
};
template <typename T>
class SegmentTree {
 public:
  SegmentTree(int sz) : n(sz), N(n << 1), h(0), data(N), chg(N, 0) {
    while (1 << h < N) {
      ++h;
    }
  }
  void build() {
    for (int i = n - 1; i > 0; --i) {
      data[i] = data[i << 1] + data[i << 1 | 1];
    }
  }
  void update(int x, long long v) {
    data[x] += v;
    if (x < n) {
      chg[x] += v;
    }
  }
  void pull(int x) {
    for (int p = x >> 1; p > 0; p >>= 1) {
      if (chg[p] == 0) {
        data[p] = data[p << 1] + data[p << 1 | 1];
      }
    }
  }
  void push(int x) {
    for (int i = h; i >= 0; --i) {
      int p = x >> i;
      if (chg[p] != 0) {
        update(p << 1, chg[p]);
        update(p << 1 | 1, chg[p]);
        chg[p] = 0;
      }
    }
  }
  void put(int l, int r, long long v) {
    l += n;
    r += n;
    auto ll = l, rr = r;
    push(ll), push(rr);
    while (l <= r) {
      if (l & 0x1) {
        update(l++, v);
      }
      if ((r & 0x1) == 0) {
        update(r--, v);
      }
      l >>= 1;
      r >>= 1;
    }
    pull(ll), pull(rr);
  }
  void put(int x, long long v) {
    x += n;
    push(x);
    data[x] = T(v);
    pull(x);
  }
  T get(int l, int r) {
    T res;
    l += n;
    r += n;
    push(l), push(r);
    while (l <= r) {
      if (l & 0x1) {
        res = res + data[l++];
      }
      if ((r & 0x1) == 0) {
        res = res + data[r--];
      }
      l >>= 1;
      r >>= 1;
    }
    return res;
  }

 private:
  int n;
  int N;
  int h;
  vector<T> data;
  vector<long long> chg;
};
class Solution {
 public:
  long long solve(vector<int>& A) {
    int n = A.size();
    long long res = 0;
    vector<vector<int>> pos(n, vector<int>{-1});
    SegmentTree<Datum> st(n + 100);
    st.build();
    for (int i = 0; i < n; ++i) {
      int x = A[i];
      int m = pos[x].size();
      st.put(i, 0);
      if (m >= 1) {
        st.put(pos[x][m - 1] + 1, i, 1);
      }
      if (m >= 3) {
        st.put(pos[x][m - 3] + 1, pos[x][m - 2], -1);
      }
      if (m >= 4) {
        st.put(pos[x][m - 4] + 1, pos[x][m - 3], 1);
      }
      auto ans = st.get(0, n);
      if (ans.val == 0) {
        res += ans.cnt;
      }
      pos[x].push_back(i);
    }
    return res;
  }
};
int main(int argc, char** argv) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  Solution sol;
  int n;
  cin >> n;
  vector<int> A(n);
  for (int i = 0; i < n; ++i) {
    cin >> A[i];
    --A[i];
  }
  cout << sol.solve(A) << '\n';
  return 0;
}
