#include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e6+2; int n,m,ans,tim,cnt; int l,r,t; int a[N],g[N],pos[N],res[N],tmp[N],tot; struct opt { int p,x; }f[N]; struct sth { int l,r,c,t,id; }q[N]; bool cmp(sth a,sth b) { if(pos[a.l] == pos[b.l] && pos[a.r] == pos[b.r]) return a.t < b.t; if(pos[a.l] == pos[b.l]) return a.r < b.r; return a.l < b.l; } void add(int col) { res[col]++; } void del(int col) { res[col]--; } void mod(int p,int &col) { int pre = a[p]; if(l <= p && p <= r) { res[a[p]]--; res[col]++; } a[p] = col; col = pre; } signed main() { scanf("%lld%lld",&n,&m); for(int i = 1;i <= n;i++) { scanf("%lld",&a[i]); tmp[++tot] = a[i]; } int k = pow(n,2.0/3.0); for(int i = 1;i <= n;i++) pos[i] = (i-1)/k+1; for(int i = 1;i <= m;i++) { int l,r,x; scanf("%lld%lld%lld",&l,&r,&x); q[++cnt] = {l,r,x,tim,cnt}; tmp[++tot] = x; for(int j = l;j <= r;j++) { tim++; f[tim].p = j; f[tim].x = x; } } sort(tmp+1,tmp+tot+1); int len = unique(tmp+1,tmp+tot+1)-tmp-1; for(int i = 1;i <= n;i++) a[i] = lower_bound(tmp+1,tmp+len+1,a[i])-tmp; for(int i = 1;i <= cnt;i++) q[i].c = lower_bound(tmp+1,tmp+len+1,q[i].c)-tmp; for(int i = 1;i <= tim;i++) f[i].x = lower_bound(tmp+1,tmp+len+1,f[i].x)-tmp; sort(q+1,q+cnt+1,cmp); l = 1; r = 0; t = 0; for(int i = 1;i <= cnt;i++) { while(l < q[i].l) del(a[l++]); while(l > q[i].l) add(a[--l]); while(r < q[i].r) add(a[++r]); while(r > q[i].r) del(a[r--]); while(t < q[i].t) { t++; mod(f[t].p,f[t].x); } while(t > q[i].t) { mod(f[t].p,f[t].x); t--; } g[q[i].id] = res[q[i].c]; } for(int i = 1;i <= cnt;i++) printf("%lld\n",g[i]); return 0; }