#include<bits/stdc++.h>
using namespace std;
int l[500001];
int r[500001];
int w[500001];
int n,q;
int a[500001];
int ans[500001];
namespace btf{
	int cnt[100001];
	deque<int> o[30001];
	int res=0;
	void ad(int x,int v){
		o[x].push_back(v);
		cnt[v]++;
		if(cnt[v]==1)res++;
	}
	void del(int x){
		int y=o[x].front();o[x].pop_front();
		cnt[y]--;
		if(cnt[y]==0)res--;
	}
	void solve(){
		for(int i=1;i<=q;i++){
			for(int j=l[i];j<=r[i];j++){
				ad(j,w[i]);
				while(o[j].size()>a[j])del(j);
			}
			ans[i]=res;
		}
		for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
		return ;
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=q;i++){
		cin>>l[i]>>r[i]>>w[i];
	}
	if(n<=25000 and q<=25000)btf::solve();
	return 0;
}