思路：双向链表+组合数学（不过你要用单调栈也没人拦着你）
我们现在先抛开题面，先换个思路。
我们现在求：这个数能做多少个区间的次大值。
我们现在设 \(l1, l2, r1, r2\) 分别为左边第一个比这个数大的 id，第二个比这个数大的 id，右边第一个比这个数大的 id，第二个比这个数大的 id。竟然是次大值，所以我们左边和右边能且仅能包含一个比这个数大的。
我们现在求区间数即为：
- 左边取一个比他大的数的个数 \(\times\) 右边取不比他大的数的个数。
- 右边取一个比他大的数的个数 \(\times\) 左边取不比他大的数的个数。
即为：
(l1 - l2) * (r1 - a[i].id)(r2 - r1) * (a[i].id - l1)
那么如何获得 \(l1, l2, r1, r2\) 呢？
如果我能直接从当前这个数找到这四个数是最好的，就是说像这样的一个链表：
要实现这样我们可以存好 id 后排序，从小到大处理，根据链表的删除机制，到某个数时，一定会成为类似上图的样子。
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
struct Node
{
ll x;
ll id;
} a[100005];
ll pre[100005], nxt[100005];
ll ans = 0;
bool cmp(Node a, Node b) {
return a.x < b.x;
}
void del(ll id)
{
nxt[pre[id]] = nxt[id];
pre[nxt[id]] = pre[id];
return ;
}
int main()
{
cin >> n;
for (ll i = 1; i <= n; i++)
{
cin >> a[i].x;
a[i].id = i;
pre[i] = i - 1;
nxt[i] = i + 1;
}
nxt[0] = 1;
pre[n + 1] = n;
sort(a + 1, a + n + 1, cmp);
for (ll i = 1; i <= n; i++)
{
ll l1, l2, r1, r2;
// left
l1 = pre[a[i].id];
if (l1) l2 = pre[l1];
else l2 = -1;
// right
r1 = nxt[a[i].id];
if (r1 != n + 1) r2 = nxt[r1];
else r2 = -1;
// solve
if (!(l2 == -1))
ans += (l1 - l2) * (r1 - a[i].id) * a[i].x;
if (!(r2 == -1))
ans += (r2 - r1) * (a[i].id - l1) * a[i].x;
del(a[i].id);
}
cout << ans << "\n";
return 0;
}