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, typename F>
string to_string(pair<T, F> p);
template <typename T, typename F, typename Tr>
string to_string(tuple<T, F, Tr> p);
template <typename T, typename F, typename Tr, typename Th>
string to_string(tuple<T, F, Tr, Th> p);
string to_string(string s) { return '"' + s + '"'; }
string to_string(char c) { return (string) "'" + c + "'"; }
string to_string(const char* p) { return to_string((string)p); }
string to_string(bool B) { return (B ? "true" : "false"); }
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < (int)v.size(); ++i) {
    if ((int)res.size() > 1) res += ", ";
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t T>
string to_string(bitset<T> bs) {
  return bs.to_string();
}
template <typename T>
string to_string(T v) {
  string res = "{";
  for (auto& el : v) {
    if ((int)res.size() > 1) res += ", ";
    res += to_string(el);
  }
  res += "}";
  return res;
}
template <typename T, typename F>
string to_string(pair<T, F> p) {
  return '(' + to_string(p.first) + ", " + to_string(p.second) + ')';
}
template <typename T, typename F, typename Tr>
string to_string(tuple<T, F, Tr> p) {
  return '(' + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ')';
}
template <typename T, typename F, typename Tr, typename Th>
string to_string(tuple<T, F, Tr, Th> p) {
  return '(' + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ')';
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
class segTree {
 public:
  struct node {
    int mn = 0, ct = 1, lazy = 0;
    void modify(int l, int r, int x) {
      mn += x;
      lazy += x;
    }
    int get(int l, int r) { return 0; }
  };
  node emp;
  node unite(const node& x, const node& y) {
    node res;
    res.mn = min(x.mn, y.mn);
    res.ct = (res.mn == x.mn ? x.ct : 0) + (res.mn == y.mn ? y.ct : 0);
    return res;
  }
  inline void push(int v, int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    int rv = v + ((mid - l + 1) << 1);
    if (tree[v].lazy != emp.lazy) {
      tree[rv].modify(mid + 1, r, tree[v].lazy);
      tree[v + 1].modify(l, mid, tree[v].lazy);
    }
    tree[v].lazy = emp.lazy;
  }
  inline void pull(int v, int rv) { tree[v] = unite(tree[v + 1], tree[rv]); }
  int n;
  vector<node> tree;
  template <typename T>
  void build(int v, int l, int r, const vector<T> vv) {
    if (l == r) {
      tree[v].modify(l, r, vv[l]);
      return;
    }
    int mid = (l + r) >> 1;
    int rv = v + ((mid - l + 1) << 1);
    build(v + 1, l, mid, vv);
    build(rv, mid + 1, r, vv);
    pull(v, rv);
  }
  node get(int v, int l, int r, int ll, int rr) {
    if (l >= ll && rr >= r) {
      return tree[v];
    }
    int mid = (l + r) >> 1;
    int rv = v + ((mid - l + 1) << 1);
    push(v, l, r);
    if (mid >= ll && mid < rr) {
      return unite(get(v + 1, l, mid, ll, rr), get(rv, mid + 1, r, ll, rr));
    }
    if (mid >= ll) {
      return get(v + 1, l, mid, ll, rr);
    }
    return get(rv, mid + 1, r, ll, rr);
  }
  template <typename R, typename... T>
  R get(int v, int l, int r, int ll, int rr, function<R(const R&, const R&)> f,
        const T&... t) {
    if (l >= ll && rr >= r) {
      return tree[v].get(l, r, t...);
    }
    int mid = (l + r) >> 1;
    int rv = v + ((mid - l + 1) << 1);
    push(v, l, r);
    if (mid >= ll && mid < rr) {
      return f(get(v + 1, l, mid, ll, rr, t...),
               get(rv, mid + 1, r, ll, rr, t...));
    }
    if (mid >= ll) {
      return get(v + 1, l, mid, ll, rr, t...);
    }
    return get(rv, mid + 1, r, ll, rr, t...);
  }
  template <typename... T>
  void modify(int v, int l, int r, int ll, int rr, const T&... t) {
    if (l >= ll && rr >= r) {
      tree[v].modify(l, r, t...);
      return;
    }
    int mid = (l + r) >> 1;
    int rv = v + ((mid - l + 1) << 1);
    push(v, l, r);
    if (mid >= ll) {
      modify(v + 1, l, mid, ll, rr, t...);
    }
    if (mid < rr) {
      modify(rv, mid + 1, r, ll, rr, t...);
    }
    pull(v, rv);
  }
  template <typename... T>
  void set_modify(int v, int l, int r, int tar, const T&... t) {
    if (l == r) {
      tree[v] = emp;
      tree[v].modify(l, r, t...);
      return;
    }
    int mid = (l + r) >> 1;
    int rv = v + ((mid - l + 1) << 1);
    push(v, l, r);
    if (mid >= tar) {
      set_modify(v + 1, l, mid, tar, t...);
    }
    if (mid < tar) {
      set_modify(rv, mid + 1, r, tar, t...);
    }
    pull(v, rv);
  }
  int find_first_exact(int v, int l, int r,
                       const function<bool(const node&)> f) {
    if (!f(tree[v])) return -1;
    if (l == r) {
      return l;
    }
    int mid = (l + r) >> 1;
    int rv = v + ((mid - l + 1) << 1);
    push(v, l, r);
    int res = -1;
    if (f(tree[v + 1])) {
      res = find_first_exact(v + 1, l, mid, f);
    } else {
      res = find_first_exact(rv, mid + 1, r, f);
    }
    assert(res != -1);
    return res;
  }
  int find_last_exact(int v, int l, int r,
                      const function<bool(const node&)> f) {
    if (!f(tree[v])) return -1;
    if (l == r) {
      return l;
    }
    int mid = (l + r) >> 1;
    int rv = v + ((mid - l + 1) << 1);
    push(v, l, r);
    int res = -1;
    if (f(tree[rv])) {
      res = find_first_exact(rv, mid + 1, r, f);
    } else {
      res = find_first_exact(v + 1, l, mid, f);
    }
    assert(res != -1);
    return res;
  }
  int find_first(int v, int l, int r, int ll, int rr,
                 const function<bool(const node&)> f) {
    if (l >= ll && rr >= r) {
      return find_first_exact(v, l, r, f);
    }
    int mid = (l + r) >> 1;
    int rv = v + ((mid - l + 1) << 1);
    push(v, l, r);
    int res = -1;
    if (mid >= ll) {
      res = find_first(v + 1, l, mid, ll, rr, f);
    }
    if (res == -1 && mid < rr) {
      res = find_first(rv, mid + 1, r, ll, rr, f);
    }
    return res;
  }
  int find_last(int v, int l, int r, int ll, int rr,
                const function<bool(const node&)> f) {
    if (l > rr || r < ll) {
      return -1;
    }
    if (l >= ll && rr >= r) {
      return find_last_exact(v, l, r, f);
    }
    int mid = (l + r) >> 1;
    int rv = v + ((mid - l + 1) << 1);
    push(v, l, r);
    int res = -1;
    if (mid < rr) {
      res = find_first(rv, mid + 1, r, ll, rr, f);
    }
    if (res == -1 && mid >= ll) {
      res = find_first(v + 1, l, mid, ll, rr, f);
    }
    return res;
  }
  segTree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(n * 2 - 1);
  }
  template <typename T>
  segTree(vector<T> v) : n((int)v.size()) {
    tree.resize(n * 2 - 1);
    build(0, 0, n - 1, v);
  }
  node get(int ind) {
    assert(ind >= 0 && ind < n);
    return get(0, 0, n - 1, ind, ind);
  }
  node get(int l, int r) {
    assert(l >= 0 && l < n && r >= 0 && r < n && r >= l);
    return get(0, 0, n - 1, l, r);
  }
  template <typename R, typename... T>
  R get(int l, int r, function<R(const R&, const R&)> f, T... t) {
    assert(l >= 0 && l < n && r >= 0 && r < n && r >= l);
    return get<R>(0, 0, n - 1, l, r, f, t...);
  }
  template <typename... T>
  void modify(int l, int r, T... t) {
    assert(l >= 0 && l < n && r >= 0 && r < n && r >= l);
    modify(0, 0, n - 1, l, r, t...);
  }
  template <typename... T>
  void set_modify(int ind, T... t) {
    assert(ind >= 0 && ind < n);
    set_modify(0, 0, n - 1, ind, ind, t...);
  }
  int find_first(int l, int r, const function<bool(const node&)> f) {
    assert(l >= 0 && l < n && r >= 0 && r < n && r >= l);
    return find_first(0, 0, n - 1, l, r, f);
  }
  int find_last(int l, int r, const function<bool(const node&)> f) {
    assert(l >= 0 && l < n && r >= 0 && r < n && r >= l);
    return find_last(0, 0, n - 1, l, r, f);
  }
  int find_first(const function<bool(const node&)> f) {
    return find_first(0, 0, n - 1, 0, n - 1, f);
  }
  int find_last(const function<bool(const node&)> f) {
    return find_last(0, 0, n - 1, 0, n - 1, f);
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  segTree st(n);
  vector<vector<int>> pos(n + 1, {-1});
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    int val = a[i];
    pos[val].push_back(i);
    int sz = (int)pos[val].size();
    (void)37;
    st.modify(pos[val][sz - 2] + 1, i, 1);
    if ((int)pos[val].size() >= 4) {
      st.modify(pos[val][sz - 4] + 1, pos[val][sz - 3], -1);
    }
    if ((int)pos[val].size() >= 5) {
      st.modify(pos[val][sz - 5] + 1, pos[val][sz - 4], +1);
    }
    auto res = st.get(0, i);
    (void)37;
    assert(res.mn >= 0);
    if (res.mn == 0) {
      (void)37;
      ans += res.ct;
    }
  }
  cout << ans << '\n';
}
