C,D c++ #雾粉与最小值# 通过单调栈获取已目前这位为最小的区间例如1 3 2，对于i=1，左边有0个<=a[i],右边有3个也就是对于len 1 2 3 的贡献都是1转换为三个等差数列，利用线段树维护，区间修改，区间查找 贡献类似于 1 2 2 2 1

1 2 3 3 2 1

1 2 1

1 1

1 这种

		modify(1,len,r,0);
		modify(1,r,1-r,1);
		modify(len-r+1,len,0,-1);

对于获取的的区间,从大到小排好，离线处理val也从大到小，对于区间min>=val一个一个加进线段树，然后查询即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define N 510101
int n;
const int mod=1e9+7;
pair<int,int> st[N];
int cnt=0;
int l[N],r[N];
int a[N];
struct node3{
	int w,le,re,id;
}p[N];
bool cmp3(node3 a,node3 b){
	return a.w<b.w;
}
int m=0;
struct node2{
	int w,l,r,dd;
	int id;
}ans[N];
bool cmp1(node2 a,node2 b){
	return a.w>b.w;
}
bool cmp2(node2 a,node2 b){
	return a.id<b.id;
}
struct node {
	int l, r;
	int sum;
	int k, d;
}t[N << 2];
int INV2 = mod - mod / 2;
int w[N];

void pushdown(node& op, int k, int d) {
//	int len = op.r - op.l + 1;
//	int qaq = (k + (k + 1ll * (len - 1) * d) % mod) % mod * len % mod * INV2 % mod;
//	op.sum = (op.sum + qaq) % mod;
//	op.k = (op.k + k) % mod, op.d = (op.d + d) % mod;
	int len = op.r - op.l + 1;
	int qaq = (k + (k + 1ll * (len - 1) * d) )  * len  /2;
	op.sum = (op.sum + qaq) ;
	op.k = (op.k + k) , op.d = (op.d + d) ;
}
void pushdown(int x){
	if (!t[x].k and !t[x].d) return;
	
	pushdown(t[x << 1], t[x].k, t[x].d);
	
	int llen = t[x << 1].r - t[x << 1].l + 1;
	t[x].k = (t[x].k + 1ll * t[x].d * llen) ;
	pushdown(t[x << 1 | 1], t[x].k, t[x].d);
	
	t[x].k = t[x].d = 0;
}
void pushup(int x) { t[x].sum = (t[x << 1].sum + t[x << 1 | 1].sum) ; }

void build(int l, int r, int x = 1) {
	t[x] = { l, r, w[l] , 0, 0 };
	if (l == r) return;
	int mid = l + r >> 1;
	build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
	pushup(x);
}

void modify(int l, int r, int k, int d, int x = 1) {
	if (l <= t[x].l and r >= t[x].r) {
		pushdown(t[x], k, d);
		return;
	}
	pushdown(x);
	int mid = t[x].l + t[x].r >> 1;
	if (r <= mid) modify(l, r, k, d, x << 1);
	else if (l > mid) modify(l, r, k, d, x << 1 | 1);
	else {
		modify(l, mid, k, d, x << 1);
		k = (k + 1ll * d * (mid - l + 1)) ;
		modify(mid + 1, r, k, d, x << 1 | 1);
	}
	pushup(x);
}

int ask(int l, int r, int x = 1) {
	if (l <= t[x].l and r >= t[x].r) return t[x].sum;
	pushdown(x);
	int mid = t[x].l + t[x].r >> 1;
	int res = 0;
	if (l <= mid) res = ask(l, r, x << 1);
	if (r > mid) res = (res + ask(l, r, x << 1 | 1)) ;
	return res;
}

void solve() {
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n);
	for(int i=1;i<=n;i++){
		if(a[i]<=st[cnt].first&&cnt!=0){
			while(a[i]<=st[cnt].first&&cnt!=0){
				r[st[cnt].second]=i;
				cnt--;
				i--;
			}
			continue;
		}
		if(a[i]>st[cnt].first&&cnt!=0){
			l[i]=st[cnt].second;
			st[++cnt]={a[i],i};
			continue;
		}
		
		if(cnt==0){
			l[i]=0;
			st[++cnt]={a[i],i};
			continue;
		}	
	}
	for(int i=1;i<=n;i++){
		//	cout<<l[i]<<' '<<r[i]<<'\n';
		int j=i;
		int le=l[i],re=r[j];
		if(re==0) re=n+1;
		int sum=re-le-1;
		i=j;
		p[++cnt].w=a[i];
		p[cnt].le=le;
		p[cnt].re=re;
		p[cnt].id=i;
	}
	sort(p+1,p+cnt+1,cmp3);
	int m=cnt;
	int q;
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>ans[i].w>>ans[i].l>>ans[i].r;
		ans[i].id=i;
	}
	sort(ans+1,ans+q+1,cmp1);
	int j=m;
	for(int i=1;i<=q;i++){
		//cout<<j<<'\n';
		while(p[j].w>=ans[i].w&&j>=1){
			int len=p[j].re-p[j].le-1;
			int l=p[j].id-p[j].le-1,r=p[j].re-p[j].id;

			modify(1,len,r,0);
			modify(1,r,1-r,1);
			modify(len-r+1,len,0,-1);
			j--;
		}
		ans[i].dd=ask(ans[i].l,ans[i].r);
	}
	sort(ans+1,ans+q+1,cmp2);
	for(int i=1;i<=q;i++){
		cout<<ans[i].dd<<'\n';
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t=1;
//	cin >> t;
	
	while (t--) {
		solve();
	}
	return 0;
}