我们考虑每个点成为区间左端点时合法的右区间范围，我们假定a是下标比i大的且值比i大的最小下标，b是下标比a大且值比i大的最小下标，那么以i为左端点的合法区间范围应是[a, b -1]。同理我们也能求出i是区间右端点时合法的区间[ql, qr]。set即可完成。
我们从左往右扫，每个点是左端点时的合法区间[l, r]应该在l插入，并且在r删除，扫到一个点i时，应询问在其合法区间[ql, qr]内有多少个合法左端点。树状数组即可完成。
复杂度O(nlog(n))

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
using namespace std;

const int N = 1e6 + 100;

int tree[N];

void insert(int id, int x) {
    for (; id < N; id += id & -id) tree[id] += x;
}

int query(int id) {
    int sum = 0;
    for (; id > 0; id -= id & -id) sum += tree[id];
    return sum;
}

int query(int l, int r) {
    return query(r) - query(l - 1);
}

int n;
int sa[N], rev[N], ql[N], qr[N];
vector<int> Inc[N], Dec[N];

void solve() {
    for (int i = 1; i <= n; i++) rev[sa[i]] = i;

    set<int> S;
    for (int i = 1; i <= n; i++) {
        int id = rev[i];
        S.insert(id);
        auto a = S.upper_bound(id);
        if (a == S.end()) continue;
        Inc[*a].push_back(id);
        a++;
        if (a != S.end()) Dec[(*a) - 1].push_back(id);
    }

    S.clear();
    for (int i = n; i >= 1; i--) {
        int id = rev[i];
        S.insert(-id);
        auto a = S.upper_bound(-id);
        if (a == S.end()) continue;
        qr[id] -= (*a);
        a++;
        if (a == S.end()) ql[id] = 1;
        else ql[id] -= (*a) - 1;
    }

    long long ans = 0;

    for (int i = 1; i <= n; i++) {
        for (int v : Inc[i]) insert(v, 1);

        if (ql[i] && qr[i]) ans += query(ql[i], qr[i]);

        for (int v : Dec[i]) insert(v, -1);
    }

    printf("%lld\n", ans);
}

int main() {
    //freopen("0.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", sa + i);
    solve();
    return 0;
}