#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> d(n, -1);
    set<int> q;
    long long ans = 0;
    for (int x : a) {
        int y = 0;
        auto it = q.lower_bound(x);
        if (it != end(q)) {
            y = max(y, d[*it]);
        }
        if (it != begin(q)) {
            y = max(y, d[*prev(it)]);
        }
        d[x] = y + 1;
        q.insert(x);
        ans += y;
    }
    cout << ans << "\n";
}

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

    solve();

    return 0;
}