RT， 万分感谢。

#include<iostream>
#include<cstdio> 
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define int long long
#define ri register int
#define rd(n) n=read()
inline int read(void)
{
    register int res=0,f=0;
    register char c=getchar();
    while(c<'0'||c>'9'){f^=(c=='-');c=getchar();}
    while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
    return f?-res:res;
}
inline void fprint(int n)
{
    if(n<0){putchar('-');n=-n;}
    if(n>9) fprint(n/10);
    putchar(n%10+'0');
}
inline void print(int n)
{
    fprint(n);
    putchar('\n');
}   
const int N=30005;
const int k=10000;
int n,m,x,y,z,ans,res,cnt,block,len,a[N];
int l[k],r[k],pos[k];
vector<int>v[k];
signed main(void)
{
	rd(n);
	for(ri i=1;i<=n;++i) rd(a[i]);
	rd(m);
	block=sqrt(n); 
	for(ri i=1;i<=block+100;++i)
	{
		l[i]=r[i-1]+1;
		r[i]=i*block; 
	}
	if(r[block]<n) 
	{
		++block;
		l[block]=r[block-1]+1;
		r[block]=n; 
	}
	for(ri i=1;i<=block;++i) 
	{
		for(ri j=l[i];j<=r[i];++j)
		{
			pos[j]=i; 
			v[i].emplace_back(a[j]);
		}	
		sort(v[i].begin(),v[i].end());
	} 
	while(m--)
	{
		rd(x); rd(y); rd(z);
		if(x>y) swap(x,y);
		ans=0;
		if(pos[x]==pos[y])
		{
			for(ri i=x;i<=y;++i)
				if(a[i]>z) ++ans;
			print(ans);
			continue;
		}
		for(ri i=x;i<=r[pos[x]];++i) if(a[i]>z) ++ans;
		for(ri i=l[pos[y]];i<=y;++i) if(a[i]>z) ++ans;
		for(ri i=pos[x]+1;i<=pos[y]-1;++i)
		{ 
			auto it=upper_bound(v[i].begin(),v[i].end(),z);
			ri ts=it-v[i].begin();
			ts=(int)v[i].size()-ts;
			ans+=ts;
		}
		print(ans);
	}
	return 0;
}
/*
17
1 5 2 4 3 6 8 7 52 3 96 3 6 5 4 8 11
4
1 17 10
8 10 6
3 7 2
17 17 100
1 5 100
*/