借教室

暴力上线段树即可，比二分+差分思路简单多了
线段树维护区间最小值然后和需要借教室的多少比较
再区间减即可

/*
线段树维护最小值 
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define N 1000006
using namespace std;
int n,m;
int R[N];
int MIN[N*8];
int lazy[N*8];
void down(int x){
    if(lazy[x]){
        MIN[x*2]-=lazy[x];
        MIN[x*2+1]-=lazy[x];
        lazy[x*2]+=lazy[x];
        lazy[x*2+1]+=lazy[x];
        lazy[x]=0;
    }
}
void buit(int bh,int l,int r)
{
    if(l==r){
        MIN[bh]=R[r];
        return;
    }
    int mid=(l+r)/2;
    buit(bh*2,l,mid);
    buit(bh*2+1,mid+1,r);
    MIN[bh]=min(MIN[bh*2],MIN[bh*2+1]);
}
int ask(int bh,int l,int r,int cl,int cr)
{
    down(bh);
    if(cl<=l&&r<=cr){
        return MIN[bh];
    }
    int mid=(l+r)/2,ans=INT_MAX;
    if(cl<=mid) ans=min(ans,ask(bh*2,l,mid,cl,cr));
    if(cr>mid) ans=min(ans,ask(bh*2+1,mid+1,r,cl,cr));
    MIN[bh]=min(MIN[bh*2],MIN[bh*2+1]);
    return ans;
}
void xg(int bh,int l,int r,int cl,int cr,int k)
{
    down(bh);
    if(cl<=l&&r<=cr){
        MIN[bh]-=k;
        lazy[bh]+=k;
        return;
    }
    int mid=(l+r)/2;
    if(cl<=mid) xg(bh*2,l,mid,cl,cr,k);
    if(cr>mid) xg(bh*2+1,mid+1,r,cl,cr,k);
    MIN[bh]=min(MIN[bh*2],MIN[bh*2+1]);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&R[i]);
    buit(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int d,s,t;
        scanf("%d%d%d",&d,&s,&t);
        int M=ask(1,1,n,s,t);
        if(M>=d){
            xg(1,1,n,s,t,d);
        }else{
            puts("-1");
            cout<<i<<"\n";
            return 0;
        }
    }
    puts("0");
    return 0;
}