#include<bits/stdc++.h>   typedef int LL;   typedef double dl;   #define opt operator   #define pb push_back   #define pii std::pair<LL,LL>   const LL maxn=2e4+9,mod=998244353,inf=0x3f3f3f3f;   LL Read(){    LL x(0),f(1); char c=getchar();    while(c< 0  || c> 9 ){     if(c== - ) f=-1; c=getchar();    }    while(c>= 0  && c<= 9 ){     x=(x<<3ll)+(x<<1ll)+c- 0 ; c=getchar();    }return x*f;   }   void Chkmin(LL &x,LL y){    if(y<x) x=y;   }   void Chkmax(LL &x,LL y){    if(y>x) x=y;   }   LL add(LL x,LL y){    return x+=y,x>=mod?x-mod:x;   }   LL dec(LL x,LL y){    return x-=y,x<0?x+mod:x;   }   LL mul(LL x,LL y){    return 1ll*x*y%mod;   }   LL Pow(LL base,LL b){    LL ret(1); while(b){     if(b&1) ret=mul(ret,base); base=mul(base,base); b>>=1;    }return ret;   }   const LL Ul=15,Ku=30;   namespace Rmq{    LL lg[maxn];    pii mx[maxn][16];    void Init(LL *A,LL N){     for(LL i=1;i<=N;++i){      mx[i][0]=pii(A[i],i);     }     for(LL i=1;i<=15;++i){      for(LL j=1;j+(1<<i)-1<=N;++j){       mx[j][i]=std::max(mx[j][i-1],mx[j+(1<<i-1)][i-1]);      }     }     for(LL i=1;i<=N;++i) lg[i]=lg[i>>1]+1;    }    LL Query(LL l,LL r){     LL len(lg[r-l+1]-1);     return std::max(mx[l][len],mx[r-(1<<len)+1][len]).second;    }   }   LL n,q;   LL a[maxn],f[16][maxn][31];   void Init(){    n=Read(); q=Read();    for(LL i=1;i<=n;++i){     a[i]=Read();    }    for(LL i=1;i<=n+1;++i){     a[i]+=i;    }   // for(LL i=1;i<=n;++i) printf( %d  ,a[i]-i); puts(  );    Rmq::Init(a,n+1);   // puts( #1 );    for(LL j=0;j<=Ul;++j){     for(LL k=0;k<=Ku;++k) f[j][n+1][k]=n+1;    }   // puts( #2 );    for(LL i=n;i>=1;--i){   //  printf( (%d) n ,i);     for(LL k=0;k<=Ku;++k){      f[0][i][k]=std::min(a[i]+k,n+1);     }     for(LL j=1;j<=Ul;++j){      for(LL k=0;k<=Ku;++k){       LL mx(0);       for(LL k1=k;k1>=0 && mx<n;--k1){        Chkmax(mx,f[j-1][Rmq::Query(i,f[j-1][i][k1])][k-k1]);       }       f[j][i][k]=mx;      }     }    }   }   void Solve(LL l,LL r,LL K){    static LL g[31];    if(l==r){     puts( 0 );     return;    }    Chkmin(K,r-l-1);    for(LL i=0;i<=Ku;++i){     g[i]=std::min(n+1,a[l]+i);    }    LL ret(1);    for(LL i=0;i<=K;++i) if(g[i]>=r){     puts( 1 );     return;    }    for(LL i=Ul;i>=0;--i){     LL flag(0);     static LL h[31];     for(LL k=K;k>=0;--k){      LL mx(0);      for(LL k1=0;k1<=k && mx<r;++k1){       Chkmax(mx,f[i][Rmq::Query(l,g[k1])][k-k1]);      }      h[k]=mx;      if(mx>=r){       flag=1; break;      }     }     if(!flag){      for(LL k=0;k<=Ku;++k) g[k]=h[k];      ret+=(1<<i);     }    }    printf( %d n ,ret+1);   // exit(0);   }   void Solve(){    while(q--){     LL l(Read()),r(Read()),K(Read());     Solve(l,r,K);    }   }   int main(){    Init();    Solve();    return 0;   }            