#include <bits/stdc++.h>
#define DIMN 1000010
using namespace std;
struct segm{
int maxi , pmaxi , sorted;
} aint[4 * DIMN];
int v[DIMN];
void build (int nod , int st , int dr){
int mid = (st + dr)/2;
if (st == dr){
aint[nod].maxi = v[st];
aint[nod].pmaxi = st;
aint[nod].sorted = 1;
return;
}
build (2 * nod , st , mid);
build (2 * nod + 1 , mid + 1 , dr);
if (aint[2 * nod].maxi >= aint[2 * nod + 1].maxi){
aint[nod].maxi = aint[2 * nod].maxi;
aint[nod].pmaxi = aint[2 * nod].pmaxi;
}
else {
aint[nod].maxi = aint[2 * nod + 1].maxi;
aint[nod].pmaxi = aint[2 * nod + 1].pmaxi;
}
/// sorted ins daca intervalul l .. r este crescator oricum
if (aint[2 * nod].sorted && aint[2 * nod + 1].sorted && v[mid] <= v[mid + 1])
aint[nod].sorted = 1;
else aint[nod].sorted = 0;
}
int qsuff (int nod , int st , int dr , int l , int r){
int mid = (st + dr) / 2 , sum = 0;
if (l <= st && dr <= r){
if (aint[nod].sorted)
return st - dr + 1;
sum = qsuff (2 * nod + 1 , mid + 1 , dr , l , r);
if (sum == min(r , dr) - (mid + 1) + 1 && v[mid] <= v[mid + 1])
sum += qsuff(2 * nod , st , mid , l , r);
return sum;
}
if (mid + 1 <= r)
sum = qsuff (2 * nod + 1 , mid + 1 , dr , l , r);
if (l <= mid && (mid + 1 > r || (sum == min(r , dr) - (mid + 1) + 1 && v[mid] <= v[mid + 1])))
sum += qsuff(2 * nod , st , mid , l , r);
return sum;
}
int maxi , pmaxi;
void qmaxi (int nod , int st , int dr , int l , int r){
int mid = (st + dr) / 2;
if (l <= st && dr <= r){
if (maxi < aint[nod].maxi){
maxi = aint[nod].maxi;
pmaxi = aint[nod].pmaxi;
}
return;
}
if (l <= mid)
qmaxi(2 * nod , st , mid , l , r);
if (mid + 1 <= r)
qmaxi (2 * nod + 1 , mid + 1 , dr , l , r);
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , q , i , l , r , k , suff , a , b , st , dr , mid;
fscanf (fin,"%d%d",&n,&q);
for (i = 1 ; i <= n ; i++){
fscanf (fin,"%d",&v[i]);
}
build (1 , 1 , n);
for (;q;q--){
fscanf (fin,"%d%d%d", &l , &r , &k);
suff = qsuff (1 , 1 , n , l , r);
r = r - suff;
if (r < l){
fprintf (fout,"1\n");
continue;
}
/// acum intre l si r exista clar niste inversiuni
maxi = -1;
pmaxi = n + 1;
qmaxi (1 , 1 , n , l , r);
a = maxi;
l = pmaxi + 1;
b = -1;
if (l <= r){
maxi = 0;
pmaxi = n + 1;
qmaxi (1 , 1 , n , l , r);
b = maxi;
}
st = r + 1;
dr = r + suff; /// cauti cel mai mare element mai mic decat a
while (st <= dr){
mid = (st + dr) / 2;
if ( a >= v[mid] )
dr = mid - 1;
else st = mid + 1;
}
if (st >= r + 1 && v[st] > b){
b = v[st];
}
fprintf (fout,"%d\n", (a + b <= k) );
}
return 0;
}
