#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,T=300,M=N/T+5,inf=1e9;
int n,m,laz[N],p[N],val[N],to[N],rs[N],st[N],ed[N],bh[N],w[N],res,sm[N];
struct nodes{
    int l,r,x;
}g[N];
vector<int>jl[N],ad[N],pl[N],q,dl[N];
void adds(int l,int r,int sm){
    int x=bh[l];
    if(l==st[x]&&r==ed[x]){
        laz[x]+=sm;
        return;
    }
    for(int i=st[x];i<=ed[x];i++)p[i]+=laz[x];
    laz[x]=0;val[x]=-inf;
    for(int i=l;i<=r;i++)p[i]+=sm;
    for(int i=st[x];i<=ed[x];i++)val[x]=max(val[x],p[i]);
}
void add(int l,int r,int sm){
    if(l>r)return;
    if(bh[l]==bh[r]){
        adds(l,r,sm);
        return;
    }
    int ll=bh[l]+1,rr=bh[r]-1;
    for(int i=ll;i<=rr;i++)laz[i]+=sm;
    adds(l,st[ll]-1,sm);adds(ed[rr]+1,r,sm);
}
int gets(int x){
    return p[x]+laz[bh[x]];
}
void add(int x){
  //  cout<<"add"<<x<<endl;
    q.insert(lower_bound(q.begin(),q.end(),x),x);
    add(x+1,m,1);
}
void del(int x){
   // cout<<"del"<<x<<endl;
    q.erase(lower_bound(q.begin(),q.end(),x));
    add(x+1,m,-1);
}
int solve(int x,int k){
    int y=gets(x);
  //  cout<<x<<"->"<<y<<endl;
    if(y+w[k]>=q.size())return m+1;
    return q[y+w[k]];
}
signed main(){
   // freopen("in.txt","r",stdin);
   // freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    memset(p,-0x3f,sizeof(p));
    for(int i=1;i<=n;i++)cin>>p[i],w[i]=p[i];
    for(int i=1;i<=m;i++)cin>>g[i].l>>g[i].r>>g[i].x,ad[g[i].l].push_back(i),pl[g[i].r+1].push_back(i);
    for(int i=1;i<N;i++)bh[i]=(i-1)/T+1,val[bh[i]]=max(val[bh[i]],p[i]);
    for(int i=1;i<M;i++)st[i]=ed[i-1]+1,ed[i]=i*T;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=bh[n];j++){
            while(val[j]+laz[j]>=0&&to[j]<=m){
                to[j]++;
                add(max(st[j],g[to[j]].l),min(ed[j],g[to[j]].r),-1);
            }
            if(st[j]>=g[i].l&&ed[j]<=g[i].r)rs[i]=max(rs[i],to[j]);
        }
        add(g[i].l,g[i].r,1);
        int ll=bh[g[i].l]+1,rr=bh[g[i].r]-1;
        if(bh[g[i].l]==bh[g[i].r]){
            for(int j=g[i].l;j<=g[i].r;j++)jl[j].push_back(i);
            continue;
        }
        for(int j=g[i].l;j<st[ll];j++)jl[j].push_back(i);
        for(int j=ed[rr]+1;j<=g[i].r;j++)jl[j].push_back(i);
    }
    q.push_back(m+1);
    for(int i=1;i<=m;i++)p[i]=0,laz[i]=0;
    for(int i=1;i<=n;i++){
        for(auto j:ad[i])add(j);
        for(auto j:pl[i])del(j);
        for(auto j:jl[i])rs[j]=max(rs[j],solve(j,i));
    }
    //for(int i=1;i<=m;i++)cout<<rs[i]<<endl;
    for(int i=1;i<=m;i++){
        res+=!sm[g[i].x];
        sm[g[i].x]++;
        dl[rs[i]].push_back(g[i].x);
        for(auto j:dl[i]){
            sm[j]--;
            res-=!sm[j];
        }
        cout<<res<<"\n";
    }
}