在绍兴市编程达人的聚会中，厌倦了求最大值的新昌小伙伴想出了一个求次大值的方案，想来考考大家。
给定一个1到n的数字各出现一次的排列a[1]、a[2]、…、a[n]，定义f(l,r)表示a[l]、a[l+1]、a[l+2]、…、a[r]中的次大值，你需要求出对于所有的1<=i<j<=n，f(i,j)的和。
【数据范围约定】
对于30%的数据，n<=100；
对于70%的数据，n<=5000；
对于100%的数据，n<=100000。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN=100005;
struct T{
int v,id; //v存放读入元素值，id存放读入顺序号
}x[MAXN];
int pre[MAXN],nxt[MAXN];
int cmp(T t1,T t2){ return t1.v<t2.v; }
void del(int p){
int L=pre[p],r=nxt[p];
nxt[L]=r; pre[r]=L;
}
int main(){
int m,n,i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&x[i].v);
x[i].id=_____①_____;
pre[i]=i-1;
nxt[i]=i+1;
}
nxt[0]=1;
pre[n+1]=n;
_____②____;
LL ans=0;
for(i=1;i<=n;i++){
LL L1,L2,r1,r2;
L1=pre[x[i].id];
if(L1) L2=pre[L1]; else L2=-1;
r1=nxt[x[i].id];
if(r1!=n+1) r2=nxt[r1]; else r2=-1;
if(L2!=-1) ans+=___③____*i;
if(r2!=-1) ans+=___④____*i;
del(_____⑤____);
}
printf("%lld",ans);
}