#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+3; const int M=1e3+4; map<int,int>num[M]; int a[N],in[N],le[M],re[M],n,m; int nd[M],lz[M]; void pushdown(int x) { if(nd[x]==0) return; for(int i=le[x];i<=re[x];i++) { num[x][a[i]]--; a[i]=lz[x]; } nd[x]=0; } signed main() { // freopen("ODT.in","r",stdin); // freopen("ODT.out","w",stdout); ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m; int siz=sqrt(n); for(int i=1;i<=n;i++) { in[i]=(i-1)/siz+1; if(le[in[i]]==0) le[in[i]]=i; re[in[i]]=i; } for(int i=1;i<=n;i++) { cin>>a[i]; num[in[a[i]]][a[i]]++; } while(m--) { int l,r,c; int ans=0; cin>>l>>r>>c; if(l>r) swap(l,r); if(in[l]==in[r]) { pushdown(in[l]); for(int i=l;i<=r;i++) { if(a[i]==c) ans++; num[in[l]][a[i]]--; a[i]=c; num[in[l]][c]++; } cout<<ans<<'\n'; } else { pushdown(in[l]); for(int i=l;i<=re[in[l]];i++) { if(a[i]==c) ans++; num[in[l]][a[i]]--; a[i]=c; num[in[l]][c]++; } // cout<<ans<<' '; for(int i=in[l]+1;i<in[r];i++) { if(nd[i]==0||lz[i]==c) ans+=min(re[i]-le[i]+1,num[i][c]); nd[i]=1; lz[i]=c; num[i][c]+=re[i]-le[i]+1; } // cout<<ans<<' '; pushdown(in[r]); for(int i=le[in[r]];i<=r;i++) { if(a[i]==c) ans++; num[in[r]][a[i]]--; a[i]=c; num[in[r]][c]++; } cout<<ans<<'\n'; } } return 0; }