#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> t;
    int m = 1;
    while (m < n) {
        m *= 2;
    }
    t.resize(2 * m, 0);

    auto qry = [&](int l, int r) {
        int s = 0;
        for (l += m, r += m; l < r; l /= 2, r /= 2) {
            if (l % 2 == 1) {
                s += t[l];
                ++l;
            }
            if (r % 2 == 0) {
                s += t[r];
                --r;
            }
        }
        if (l == r) {
            s += t[l];
        }
        return s;
    };

    auto upd = [&](int k) {
        k += m;
        t[k] = 1;
        for (int i = k / 2; i; i /= 2) {
            t[i] = t[2 * i] + t[2 * i + 1];
        }
    };

    auto searchr = [&](int k) {
        int val = qry(0, k) + 1;
        int p = 1;
        int s = 0;
        while (p < m) {
            if (s + t[2 * p] < val) {
                s += t[2 * p];
                p = 2 * p + 1;
            } else {
                p = 2 * p;
            }
        }
        s += t[p];
        if (s < val) {
            return m;
        } else {
            return p - m;
        }
    };

    auto searchl = [&](int k) {
        int val = qry(k, m - 1) + 1;
        int p = 1;
        int s = 0;
        while (p < m) {
            if (s + t[2 * p + 1] < val) {
                s += t[2 * p + 1];
                p = 2 * p;
            } else {
                p = 2 * p + 1;
            }
        }
        s += t[p];
        if (s < val) {
            return -1;
        } else {
            return p - m;
        }
    };

    vector<int> d(n, -1);
    long long ans = 0;
    for (int x : a) {
        int y = 0;
        int l = searchl(x), r = searchr(x);
        if (l >= 0) {
            y = max(y, d[l]);
        }
        if (r < n) {
            y = max(y, d[r]);
        }
        d[x] = y + 1;
        upd(x);
        ans += y;
    }
    cout << ans << "\n";
}

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

    solve();

    return 0;
}