%你考时错误估计了复杂度，自信认为一秒7e8。虽然后来写了正解但还是想卡过莫队。
record
思路是莫队+树状数组。
区间内岛屿数=区间内大于x的数量-区间中本身和右边均大于x的数量。

#include<bits/stdc++.h>
#define maxn 200005
#define lowbit(x) (x&-x)
using namespace std;
int n,m;
struct ask{
	int l,r,x,num;
}q[maxn];
int ans_all[maxn];
int len,cnt,from[maxn];
inline void getblock(){
	len=sqrt(n);
	for(int i=1;i<=n;i++){
		if(i%len==1)cnt++;
		from[i]=cnt;
	}
}
inline bool cmp(ask x,ask y){
	if(from[x.l]^from[y.l])return from[x.l]<from[y.l];
	if((from[x.l]&1)==0)return x.r<y.r;
	else return x.r>y.r;
}
int lsh[maxn*2],cnt_l;
int c[maxn*2];
int a[maxn];
inline void update(int x,int y){
	if(x==0)return;
	while(x<=cnt_l){
		c[x]+=y;
		x+=lowbit(x);
	}
}
inline int sum(int x){
	int ans=0;
	while(x>0){
		ans+=c[x]; 
		x-=lowbit(x);
	} 
	return ans;
}
int ls[maxn*2];
signed main(){
	ios::sync_with_stdio(false);cin.tie(0); 
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		lsh[++cnt_l]=a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>q[i].l>>q[i].r>>q[i].x; 
		lsh[++cnt_l]=q[i].x;q[i].num=i;
	}
	sort(lsh+1,lsh+cnt_l+1);
	cnt_l=unique(lsh+1,lsh+cnt_l+1)-lsh-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+cnt_l+1,a[i])-lsh;
	for(int i=1;i<=m;i++)q[i].x=lower_bound(lsh+1,lsh+cnt_l+1,q[i].x)-lsh;
	getblock();
	sort(q+1,q+m+1,cmp);
	register int l=0,r=0;
	for(int i=1;i<=m;i++){
		while(r<q[i].r){
			r++;
			if(a[r]<=a[r-1]||a[r-1]==a[r])continue;
			update(a[r-1],1);
			update(a[r],-1);
		}
		while(r>q[i].r){
			r--;
			if(a[r+1]<=a[r]||a[r]==a[r+1])continue;
			update(a[r+1],1);
			update(a[r],-1);
		}
		while(l<q[i].l){
			l++;
			if(a[l-1]<=a[l]||a[l]==a[l-1])continue;
			update(a[l],-1);
			update(a[l-1],1);
		}
		while(l>q[i].l){
			l--;
			if(a[l]<=a[l+1]||a[l]==a[l+1])continue;
			update(a[l],-1);
			update(a[l+1],1);
		}
		ans_all[q[i].num]=sum(q[i].x)+1;
	}
	for(int i=1;i<=m;i++)cout<<ans_all[i]<<'\n';
	return 0;
}