站外题，T了一个点，其他点都快飞了，它连2s都过不了，求卡常，过了关。

#include<bits/stdc++.h>
using namespace std;
namespace IO{
	char ibuf[(1<<20)+1],*iS,*iT;
	#if ONLINE_JUDGE
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
	#define gh() getchar()
	#endif
	inline long long read(){
		char ch=gh();
		long long x=0;
		bool t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
}
using IO::read;
const int N=1e5+5;
long long h[N],x,y,s;
int stk[N],rs[N],ls[N],K,top,sum[N],n,m;
void build(){
    for (register int i=1;i<=n;i++){
	  	int k=top;
	 	while (k>0 && h[stk[k]]>h[i]) k--;
	  	if(k) rs[stk[k]]=i;
	  	if(k<top) ls[i]=stk[k+1];
	  	stk[++k]=i;
	  	top=k;
	}
	return;
}
void dfs(register int u,register int fa){
	if(u) dfs(rs[u],u),dfs(ls[u],u),sum[u]++,sum[fa]+=sum[u];
	return;
}
struct wbx{
	int l,r,id;
	long long v;
}q[N];
bool cmp(wbx x,wbx y){
	return x.v<y.v;
}
long long ans[N];
long long midnight(register long long x,register long long y,register long long s){
	if(s>=x && s>=y) return ((s-x+1)+(s-y+1))*(y-x+1)>>1;
	if(s>=x) return ((s-x+1)+1)*(s-x+1)>>1;
	return 0;
}
void find(register int u,register int t){//当前分支解决到第 t 个问题 
	if(!u) return;
	while(t<=m && q[t].v<=h[u]){
		x=q[t].l,y=q[t].r,s=sum[u];
		if(s>=x && s>=y) ans[q[t].id]+=((s-x+1)+(s-y+1))*(y-x+1)>>1;
		else if(s>=x) ans[q[t].id]+=((s-x+1)+1)*(s-x+1)>>1;
		t++;
	}
	find(ls[u],t);
	find(rs[u],t);
	return;
}
int main(){
	n=read();
	for(register int i=1;i<=n;i++) h[i]=read();
	build(),dfs(stk[1],0);
	m=read();
	for(register int i=1;i<=m;i++)
		q[i].v=read(),q[i].l=read(),q[i].r=read(),q[i].id=i;
	sort(q+1,q+1+m,cmp);
	find(stk[1],1);
	for(register int i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
    return 0;
}
/*
12
1 2 3 1 2 3 4 3 4 1 2 3
1
2 3 5
*/