#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
template<class T>
struct range_add_range_sum_query_solver{
int n;
vector<T> data0, data1;
range_add_range_sum_query_solver(){ }
// O(n)
range_add_range_sum_query_solver(int n): n(n), data0(n), data1(n){ }
// O(n)
range_add_range_sum_query_solver(int n, T init): range_add_range_sum_query_solver(vector<T>(n, init)){ }
// O(n)
range_add_range_sum_query_solver(const vector<T> &v): n((int)v.size()), data0(n), data1(v){
for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data1[i + (i & -i) - 1] += data1[i - 1];
}
void update(int ql, int qr, T x){
assert(0 <= ql && ql <= qr && qr <= n);
if(ql == qr) return;
for(auto l = ql + 1; l <= n; l += l & -l) data0[l - 1] += x, data1[l - 1] -= ql * x;
for(auto r = qr + 1; r <= n; r += r & -r) data0[r - 1] -= x, data1[r - 1] += qr * x;
}
T pref(int qr) const{
assert(0 <= qr && qr <= n);
T sum0 = {}, sum1 = {};
for(auto r = qr; r > 0; r -= r & -r) sum0 += data0[r - 1], sum1 += data1[r - 1];
return qr * sum0 + sum1;
}
T query(int l, int r) const{
assert(0 <= l && l <= r && r <= n);
return pref(r) - pref(l);
}
template<class output_stream>
friend output_stream &operator<<(output_stream &out, const range_add_range_sum_query_solver<T> &solver){
out << "[";
for(auto i = 0; i < solver.n; ++ i){
out << solver.query(i, i + 1);
if(i != solver.n - 1) out << ", ";
}
return out << ']';
}
};
const int N = 2e5 + 5;
range_add_range_sum_query_solver <int> seg(2 * N);
int n;
int a[N];
vi b[N];
void compress(){
vi b(a + 1, a + n + 1);
sort(bend(b));
b.erase(unique(bend(b)), b.end());
ForE(i, 1, n){
a[i] = lower_bound(bend(b), a[i]) - b.begin() + 1;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
cin >> n;
ForE(i, 1, n){
cin >> a[i];
}
compress();
ForE(i, 1, n){
b[a[i]].emplace_back(i);
}
ll ans = 0;
ForE(val, 1, n){
vpii updates;
updates.emplace_back(0 + N, 1 + N);
seg.update(0 + N, 1 + N, 1);
int sum = 0;
int l = 1;
Fora(i, b[val]){
int r = i - 1;
if (l <= r){
int vall = 2 * sum - r, valr = 2 * sum - l;
for (int j = valr; j >= vall; j--){
int tans = seg.pref(j + N);
if (tans == 0){
break;
}
ans += tans;
}
updates.emplace_back(vall + N, valr + 1 + N);
seg.update(vall + N, valr + 1 + N, 1);
}
l = r + 1;
sum++;
}
int r = n;
int vall = 2 * sum - r, valr = 2 * sum - l;
for (int j = valr; j >= vall; j--){
int tans = seg.pref(j + N);
if (tans == 0){
break;
}
ans += tans;
}
Fora(update, updates){
seg.update(update.fi, update.se, -1);
}
}
cout << ans << endl;
}
/*
==================================================+
INPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
