题解

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

int64_t ans = 0;
int N;

void add_contribution(const vector<int>& h) {
	vector<int> with_h(N+1);
	for (int i = 0; i < N; ++i) with_h[h[i]] = i;
	set<int> present;
	for (int cur_h = N; cur_h; --cur_h) {
		auto it = present.insert(with_h[cur_h]).first;
		if (next(it) != end(present)) ans += *next(it)-*it+1;
	} 
}

void add_contribution_ll(const vector<int>& h) {
	vector<int> with_h(N+1);
	for (int i = 0; i < N; ++i) with_h[h[i]] = i;
	vector<int> pre(N), nex(N);
	for (int i = 0; i < N; ++i) {
		pre[i] = i-1;
		nex[i] = i+1;
	}
	for (int cur_h = 1; cur_h <= N; ++cur_h) {
		int pos = with_h[cur_h];
		int p = pre[pos], n = nex[pos];
		if (n != N) ans += n-pos+1, pre[n] = p;
		if (p != -1) nex[p] = n;
	}
}

void add_contribution_alt(const vector<int>& h) {
	stack<int> stk;
	for (int i = N-1; i >= 0; --i) {
		while (!stk.empty() && h[stk.top()] < h[i]) stk.pop();
		if (!stk.empty()) ans += stk.top()-i+1;
		stk.push(i);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N;
	vector<int> h(N); for (int& i: h) cin >> i;
	add_contribution(h);
	reverse(begin(h), end(h));
	add_contribution(h);
	cout << ans << "\n";
}