#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
int n,a[N];
int B,bel[N],L[N],R[N];
int m,l[N],r[N],ele[N];
inline int read()
{
    int X=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){X=(X<<1)+(X<<3)+ch-'0';ch=getchar();}
    return X;
}
int eff[N];
int b[N];
int tag=0,h=0;
void ins(int o,int i,int opt)
{
    if(l[i]<=L[o]&&R[o]<=r[i])tag+=opt;
    else if(l[i]<=R[o]&&r[i]>=L[o])
    {
        for(int x=max(l[i],L[o]);x<=min(r[i],R[o]);x++)b[x]-=opt;
        h=0;
        for(int x=L[o];x<=R[o];x++)h=max(h,b[x]);
    }
}
int s[N];
int cov[N],tot=0;
int dol[N],cnt=0;
int lef[N];
void solve(int o)
{
    //整块的答案
    for(int i=L[o];i<=R[o];i++)b[i]=a[i];
    tag=0,h=0;
    for(int i=L[o];i<=R[o];i++)h=max(h,b[i]);
    int j=0;
    tot=0;cnt=0;
    for(int i=1;i<=m;i++)
    {
        ins(o,i,-1);
        while(j<=m&&h>tag)
        {
            j++;
            ins(o,j,1);
        }
        s[i]=s[i-1];
        if(L[i]<=L[o]&&R[o]<=R[i])
        {
            eff[i]=max(eff[i],j);
            s[i]++;
            cov[++tot]=i;
        }
        else if(l[i]<=R[o]&&r[i]>=L[o])
        {
            dol[++cnt]=i;
            lef[cnt]=tot;
        }
    }
    for(int p=L[o];p<=R[p];p++)
    {
        h=a[p];
        int j=0;
        for(int i=1;i<=cnt;i++)
        {
            h+=s[dol[i]]-s[dol[i-1]];
            if(L[dol[i]]<=p&&p<=R[dol[i]])
            {
                h++;
                while(j<cnt&&h>0)
                {
                    j++;
                    h-=s[dol[j]]-s[dol[j-1]]+(L[dol[j]]<=p&&p<=R[dol[j]]);
                }
                if(h>0)
                {
                    if(h>s[m]-s[dol[j]])eff[dol[i]]=m+1;
                    else eff[dol[i]]=max(eff[dol[i]],cov[lef[j]+h]);
                    continue;
                }
                if(l[dol[j]]<=p&&r[dol[j]]>=p)eff[dol[i]]=max(eff[dol[i]],h<0?cov[lef[j]+h+1]:dol[j]);
                else eff[dol[i]]=max(eff[dol[i]],cov[lef[j]+h]);
            }
        }
    }
}
struct node
{
    int x,v;
};
vector<node> upd[N];
int t[N];
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=m;i++)l[i]=read(),r[i]=read(),ele[i]=read();
    B=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        bel[i]=(i-1)/B+1;
        R[bel[i]]=i;
        if(!L[bel[i]])L[bel[i]]=i;
    }
    for(int o=1;o<=bel[n];o++)solve(o);
    for(int i=1;i<=m;i++)
    {
        upd[i].push_back((node){ele[i],1});
        upd[eff[i]].push_back((node){ele[i],-1});
    }
    int now=0;
    for(int i=1;i<=m;i++)
    {
        for(auto U:upd[i])
        {
            int x=U.x,v=U.v;
            if(t[x]==0||t[x]+v==0)now+=v;
            t[x]+=v;
        }
        printf("%d\n",now);
    }
    return 0;
}