#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for (int& x : a) {
        cin >> x;
        --x;
    }

    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        v[a[i]] = i;
    }

    stack<int> st;
    vector<int> l(n, -1), r(n, n);
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && v[i] < v[st.top()]) {
            st.pop();
        }
        if (!st.empty()) {
            l[i] = st.top();
        }
        st.push(i);
    }
    while (!st.empty()) {
        st.pop();
    }
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && v[i] < v[st.top()]) {
            st.pop();
        }
        if (!st.empty()) {
            r[i] = st.top();
        }
        st.push(i);
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += r[i] - l[i] - 2;
    }
    cout << ans << "\n";
}

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

    solve();

    return 0;
}