#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define upd(x,y) (mx[x]+=y,tag[x]+=y)
#define calc(x,y) (ans[x]=max(ans[x],y))
struct node{
	int l,r,d;
	node(int l=0,int r=0,int d=0):l(l),r(r),d(d){}
};
int n,m,b,t,l,r,k,col,sum[100001],ans[100001],a[100001],st[321],ed[321],bel[100001],val[100001],cnt[100001],mx[2001],tag[2001];
vector <int> all,v[321],add[100001],del[100001];
vector <node> w[321];
void push_down(int rt){
	upd(rt*2,tag[rt]);
	upd(rt*2+1,tag[rt]);
	tag[rt]=0;
}
void build(int rt,int l,int r){
	tag[rt]=0;
	if(l==r) return void(mx[rt]=a[l]);
	build(rt*2,l,mid);
	build(rt*2+1,mid+1,r);
	mx[rt]=max(mx[rt*2],mx[rt*2+1]);
}
void update(int rt,int l,int r,int L,int R,int v){
	if(L<=l&&r<=R) return void(upd(rt,v));
	push_down(rt);
	if(L<=mid) update(rt*2,l,mid,L,R,v);
	if(R>mid) update(rt*2+1,mid+1,r,L,R,v);
	mx[rt]=max(mx[rt*2],mx[rt*2+1]);
}
int main(){
	scanf("%d%d",&n,&m),b=sqrt(n),t=(n-1)/b+1;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),bel[i]=(i-1)/b+1;
	for(int i=1;i<=t;i++) st[i]=(i-1)*b+1,ed[i]=min(n,i*b);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&l,&r,&val[i]);
		if(bel[l]==bel[r]) w[bel[l]].push_back(node(l,r,i));
		else{
			w[bel[l]].push_back(node(l,ed[bel[l]],i));
			w[bel[r]].push_back(node(st[bel[r]],r,i));
			for(int j=bel[l]+1;j<bel[r];j++) w[j].push_back(node(st[j],ed[j],i));
		}
	}
	for(int i=1;i<=t;i++){
		for(int j=0;j<=ed[i]-st[i];j++) v[j].clear();
		build(1,st[i],ed[i]);
		memset(sum,0,sizeof(sum)),k=-1,all.clear();
		for(auto j:w[i]){
			update(1,st[i],ed[i],j.l,j.r,1);
			if(j.l==st[i]&&j.r==ed[i]){
				while(k<w[i].size()&&mx[1]>0||k==-1){
					k++;
					if(k<w[i].size()) update(1,st[i],ed[i],w[i][k].l,w[i][k].r,-1);
				}
				sum[j.d]++,all.push_back(j.d);
				calc(j.d,w[i].size()!=k?w[i][k].d-1:m);
			}
			else for(int l=j.l;l<=j.r;l++) v[l-st[i]].push_back(j.d);
		}
		for(int j=1;j<=m;j++) sum[j]+=sum[j-1];
		for(int j=0;j<=ed[i]-st[i];j++){
			int lim=a[j+st[i]],k=0;
			for(int l=0;l<v[j].size();l++){
				while(k<v[j].size()&&k-l+sum[v[j][k]]-sum[v[j][l]]<lim) k++;
				if(k<v[j].size()){
					if(k-l+sum[v[j][k]]-sum[v[j][l]]<=lim) calc(v[j][l],v[j][k]-1);
					else calc(v[j][l],all[lim+sum[v[j][l]]-k+l]-1);
				}
				else{
					if(k-l+sum[m]-sum[v[j][l]]<=lim) calc(v[j][l],m);
					else calc(v[j][l],all[lim+sum[v[j][l]]-k+l]-1);
				}
			}
		}
	}
	for(int i=1;i<=m;i++) add[i].push_back(val[i]),del[ans[i]].push_back(val[i]);
	for(int i=1;i<=m;i++){
		for(auto j:add[i]) if(!cnt[j]++) col++;
		printf("%d\n",col);
		for(auto j:del[i]) if(!--cnt[j]) col--;
	}
	return 0;
}