#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define pii pair < int, int >
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
using namespace std;
const int N = 1e6+10, Q = 1e6+10;
const int inf = 1e9+10;
const int logN = 20, maxN = (1<<logN), stpos = maxN - 1;
pii T1[(maxN<<1)];
int T2[(maxN<<1)];
int n, q;
int val[N];
pii sortedval[N];
set < int > s;
pair < pii, int > queries[Q];
int rastavljeni_size[Q];
pair < pii, pii > cur_rastavljeni_val[Q];
vector< int > qu[N];
int saz[N];
int maxsaz;
int Tsazeti[(maxN<<1)];
unordered_map < int, int > sazimanje;
int T2predicted[(maxN<<1)];
pii Tlr[(maxN<<1)];
int curpos[Q];
pair < bool, bool > lrchi[Q];
void merge1( int i ) {
T1[i].F = max(T1[i*2 + 1].F, T1[i*2 + 2].F);
T1[i].S = max(T1[i*2 + 1].S, T1[i*2 + 2].S);
if(T2predicted[i] != 0) T1[i].S = max(T1[i].S, T1[i*2 + 1].F + T2predicted[i]);
}
void updateclean1( int i, int v ) {
i += stpos;
T1[i] = mp(v, 0);
Tsazeti[i] = sazimanje[T1[i].F];
T2predicted[i] = 0;
while(i != 0) {
i = (i - 1) / 2;
T1[i].F = max(T1[i*2 + 1].F, T1[i*2 + 2].F);
T1[i].S = 0;
Tsazeti[i] = max(Tsazeti[i*2 + 1], Tsazeti[i*2 + 2]);
T2predicted[i] = 0;
}
return;
}
void reload1( int i ) {
i += stpos;
while(i != 0) {
i = (i - 1) / 2;
// cout <<"K" << i << " " << T1[i].S << "\n";
merge1(i);
}
}
void merge2( int i ) {
T2[i] = max(T2[i*2 + 1], T2[i*2 + 2]);
}
void update2( int i, int v ) {
i += stpos;
T2[i] = v;
while(i) {
i = (i - 1) / 2;
merge2(i);
}
}
void buildT1() {
s.clear();
int cur, sazpos = 0;
for(int i = 0; i < n; i++) update2(i, -inf);
for(int i = 0; i < n; i++) updateclean1(i, val[i]);
int curmaxnode = stpos + n - 1, curminnode = stpos;
while(curminnode != 0) {
curmaxnode = (curmaxnode - 1) / 2;
curminnode = (curminnode - 1) / 2;
for(int i = curminnode; i <= curmaxnode; i++) {
qu[Tsazeti[i*2 + 1]].push_back(i);
}
}
for(int i = 0; i < maxsaz; i++) {
while(!qu[i].empty()) {
cur = qu[i].back();
// cout << "XX" << i << " " << cur << " ";
qu[i].pop_back();
T2predicted[cur] = T2[cur * 2 + 2];
// cout << T2predicted[cur] << "\n";
}
while(sazpos != n && saz[sortedval[sazpos].S] <= i) {
update2(sortedval[sazpos].S, sortedval[sazpos].F);
sazpos++;
}
}
for(int i = 0; i < n; i++) reload1(i);
}
void next_step( int i ) {
// cout << i << "\n";
if(lrchi[i] == mp((bool) 1, (bool) 1) || (Tlr[curpos[i]].F >= queries[i].F.F && Tlr[curpos[i]].S <= queries[i].F.S)
|| Tlr[curpos[i]].F >= queries[i].F.S || Tlr[curpos[i]].S <= queries[i].F.F) {
if(curpos[i]&1) lrchi[i] = mp(1, 0);
else lrchi[i] = mp(1, 1);
curpos[i] = (curpos[i] - 1) / 2;
return;
}
if(!lrchi[i].F) {
lrchi[i] = mp(0, 0);
curpos[i] = curpos[i] * 2 + 1;
return;
}
lrchi[i] = mp(0, 0);
curpos[i] = curpos[i] * 2 + 2;
}
void task() {
cin >> n >> q;
for(int i = 0; i < n; i++) {
cin >> val[i];
sortedval[i].F = val[i];
sortedval[i].S = i;
}
sort(sortedval, sortedval + n);
for(int i = 1; i < n; i++) {
// cout << sortedval[i].F << " " << sortedval[i - 1].F << "\n";
saz[sortedval[i].S] = saz[sortedval[i - 1].S] + 1;
if(sortedval[i].F == sortedval[i - 1].F) saz[sortedval[i].S]--;
sazimanje[sortedval[i].F] = saz[sortedval[i].S];
}
maxsaz = saz[sortedval[n - 1].S] + 1;
for(int i = 0; i < q; i++) {
cin >> queries[i].F.F >> queries[i].F.S >> queries[i].S;
queries[i].F.F--;
}
// for(int i = 0; i < q; i++) {
// cout << i << ":\n";
// for(int j = 0; j < (int) rastavljeni[i].size(); j++) {
// cout << rastavljeni[i][j] << " ";
// }
// cout << "\n";
// }
buildT1();
for(int i = 0; i < n; i++) update2(i, -inf);
for(int i = 0; i < q; i++) {
curpos[i] = 0;
lrchi[i] = mp(0, 0);
while((lrchi[i] != mp((bool) 1, (bool) 1) || curpos[i] != 0) && !(Tlr[curpos[i]].F >= queries[i].F.F && Tlr[curpos[i]].S <= queries[i].F.S)) next_step(i);
cur_rastavljeni_val[i] = mp(T1[curpos[i]], mp(1, Tsazeti[curpos[i]]));
next_step(i);
while((lrchi[i] != mp((bool) 1, (bool) 1) || curpos[i] != 0) && !(Tlr[curpos[i]].F >= queries[i].F.F && Tlr[curpos[i]].S <= queries[i].F.S)) next_step(i);
if(lrchi[i] != mp((bool) 1, (bool) 1) || curpos[i] != 0) qu[cur_rastavljeni_val[i].S.S].push_back(i);
}
int sazpos = 0, cur;
pair < pii, pii > temp;
int curTnode;
for(int i = 0; i < maxsaz; i++) {
while(!qu[i].empty()) {
// cout << "X " << i << "\n";
cur = qu[i].back();
// cout << cur << ":\n";
// cout << cur_rastavljeni_val[cur].F.F << " " << cur_rastavljeni_val[cur].F.S << " " << cur_rastavljeni_val[cur].S.F << " " << cur_rastavljeni_val[cur].S.S << "\n";
curTnode = curpos[cur];
qu[i].pop_back();
// cout << cur_rastavljeni_val[cur].F.F << " " << cur_rastavljeni_val[cur].F.S << " " << cur_rastavljeni_val[cur].S.F << " " << cur_rastavljeni_val[cur].S.S << "\n";
temp.F.F = max(cur_rastavljeni_val[cur].F.F, T1[curTnode].F);
temp.F.S = max(cur_rastavljeni_val[cur].F.S, T1[curTnode].S);
temp.F.S = max(temp.F.S, cur_rastavljeni_val[cur].F.F + T2[curTnode]);
temp.S.F = cur_rastavljeni_val[cur].S.F + 1;
temp.S.S = max(cur_rastavljeni_val[cur].S.S, Tsazeti[curTnode]);
cur_rastavljeni_val[cur] = temp;
next_step(cur);
while((lrchi[cur] != mp((bool) 1, (bool) 1) || curpos[cur] != 0) && !(Tlr[curpos[cur]].F >= queries[cur].F.F && Tlr[curpos[cur]].S <= queries[cur].F.S)) next_step(cur);
if(lrchi[cur] != mp((bool) 1, (bool) 1) || curpos[cur] != 0) qu[cur_rastavljeni_val[cur].S.S].push_back(cur);
// cout << i << "\n";
// cout << "\n";
}
while(sazpos != n && saz[sortedval[sazpos].S] <= i) {
update2(sortedval[sazpos].S, sortedval[sazpos].F);
sazpos++;
// cout << i << "\n";
}
}
// cout << n << "\n";
// for(int i = 0; i < n; i++) cout << Tsazeti[i + stpos] << " ";
// cout << "\n";
for(int i = 0; i < n; i++) updateclean1(i, 0);
for(int i = 0; i < q; i++) cout << (cur_rastavljeni_val[i].F.S <= queries[i].S) << "\n";
curpos[10] = 0;
queries[10] = mp(mp(0, 3), 1);
lrchi[10] = mp(0, 0);
}
int main( void ) {
FIO;
for(int i = 0; i < maxN; i++) Tlr[i + stpos] = mp(i, i + 1);
for(int i = stpos - 1; i >= 0; i--) {
Tlr[i].F = Tlr[i*2+1].F;
Tlr[i].S = Tlr[i*2+2].S;
}
int tt = 1;
while(tt--) task();
return 0;
}
