#include <bits/stdc++.h>
using namespace std;

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int N = 1000010;
int a[N];
int l[N], r[N], cnt[50 * N], ls[50 * N], rs[50 * N];
int idx;

void add(int p, int &q, int l, int r, int x, int v) {
    cnt[q = ++idx] = cnt[p];
    ls[q] = ls[p];
    rs[q] = rs[p];

    if (l == r) {
        cnt[q] += v;
        return;
    } 

    int m = l + r >> 1;
    if (x <= m) {
        add(ls[p], ls[q], l, m, x, v);
    } else {
        add(rs[p], rs[q], m + 1, r, x, v);
    }
    cnt[q] = cnt[ls[q]] + cnt[rs[q]];
}

int query(int p, int q, int l, int r, int x, int y) {
    if (l > y || r < x) {
        return 0;
    } 
    if (l >= x && r <= y) {
        return cnt[q] - cnt[p];
    }

    int m = l + r >> 1;
    return query(ls[p], ls[q], l, m, x, y) + query(rs[p], rs[q], m + 1, r, x, y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<int> stk;
    for (int i = 1; i <= n; i++) {
        if (stk.empty()) {
            stk.push_back(i);
        }
        while (!stk.empty() && a[i] > a[stk.back()]) {
            stk.pop_back();
        }
        if (!stk.empty() && i != 1) {
            l[i] = stk.back();
        }
        stk.push_back(i);
    }   

    stk.clear();
    for (int i = 1; i <= n; i++) {
        r[i] = n + 1;
    }
    for (int i = n; i >= 1; i--) {
        if (stk.empty()) {
            stk.push_back(i);
        }
        while (!stk.empty() && a[i] > a[stk.back()]) {
            stk.pop_back();
        }
        if (!stk.empty() && i != n) {
            r[i] = stk.back();
        }
        stk.push_back(i);
    }

    // for (int i = 1; i <= n; i++) {
    //     cerr << l[i] << " \n"[i == n];
    // }
    vector<int> root(n + 2);
    for (int i = 1; i <= n; i++) {
        add(root[i - 1], root[i], 0, n + 1, l[i], 1);
    }

    i64 ans = n - 1;
    // int ans = 0;
    for (int i = 1; i < n; i++) {
        int R = (r[i] != n + 1 ? r[i] : n);
        if (R >= i + 1) {
            ans += query(root[i + 1], root[R], 0, n + 1, 0, i);
        }
        // cerr << i << " " << r[i] << " " << query(root[i], r[i] != n + 1 ? root[r[i] - 1] : root[n - 1], 0, n + 1, 0, i) << "\n";
    }

    cout << ans << "\n";

    return 0; 
}