#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cassert>
#include <unordered_map>
#include <bitset>
#include <unordered_set>
using namespace std;
#define pb push_back
#define pp pop_back
#define f first
#define s second
#define mp make_pair
#define sz(a) (int)((a).size())
#ifdef _WIN32
# define I64 "%I64d"
#else
# define I64 "%lld"
#endif
#define fname "."
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pi;
typedef pair < int, ull > pu;
typedef pair < ll, ll > pl;
const int inf = (int)1e9 + 123;
const int MAX_N = (int)1e6 + 123;
const int mod = (int)1e9 + 7;
int n;
int a[MAX_N];
// --------- segment tree for minimum
pi t[4 * MAX_N];
void build(int v = 1, int tl = 1, int tr = n) {
if (tl == tr) {
t[v] = mp(a[tl], tl);
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
t[v] = min(t[v * 2], t[v * 2 + 1]);
}
void update(int x, int y, int v = 1, int tl = 1, int tr = n) {
if (tl == tr) {
t[v] = mp(y, tl);
return;
}
int tm = (tl + tr) / 2;
if (x <= tm)
update(x, y, v * 2, tl, tm);
else
update(x, y, v * 2 + 1, tm + 1, tr);
t[v] = min(t[v * 2], t[v * 2 + 1]);
}
pi get(int l, int r, int v = 1, int tl = 1, int tr = n) {
if (l > r || tl > r || l > tr)
return mp(inf, -1);
if (tl >= l && tr <= r)
return t[v];
int tm = (tl + tr) / 2;
return min(get(l, r, v * 2, tl, tm), get(l, r, v * 2 + 1, tm + 1, tr));
}
// --------- maximum of sum of pairs
struct node {
int maxiSum, maxiF, maxiS, pushVal;
node operator + (const node &b) {
node res = node({-inf - inf, -inf, -inf, -1});
res.maxiF = max(maxiF, b.maxiF);
res.maxiS = max(maxiS, b.maxiS);
res.maxiSum = max(maxiSum, b.maxiSum);
return res;
}
} mx[4 * MAX_N];
void buildMax(int v = 1, int tl = 1, int tr = n) {
mx[v] = node({-inf - inf, -inf, -inf, -1});
if (tl == tr) {
return;
}
int tm = (tl + tr) / 2;
buildMax(v * 2, tl, tm);
buildMax(v * 2 + 1, tm + 1, tr);
}
void push(int v, int tl, int tr) {
if (mx[v].pushVal == -1)
return;
mx[v].maxiF = mx[v].pushVal;
mx[v].maxiSum = mx[v].maxiS + mx[v].pushVal;
if (tl != tr) {
mx[v * 2].pushVal = mx[v * 2 + 1].pushVal = mx[v].pushVal;
}
mx[v].pushVal = -1;
}
void updateMax(int l, int r, int newVal, bool tp, int v = 1, int tl = 1, int tr = n) {
push(v, tl, tr);
if (l > r || tl > r || l > tr)
return;
if (tl >= l && tr <= r) {
if (!tp) {
mx[v].pushVal = newVal;
push(v, tl, tr);
} else {
assert(tl == tr);
mx[v].maxiS = newVal;
mx[v].maxiSum = mx[v].maxiF + mx[v].maxiS;
}
return;
}
int tm = (tl + tr) / 2;
updateMax(l, r, newVal, tp, v * 2, tl, tm);
updateMax(l, r, newVal, tp, v * 2 + 1, tm + 1, tr);
mx[v] = mx[v * 2] + mx[v * 2 + 1];
}
node getMax(int l, int r, int v = 1, int tl = 1, int tr = n) {
push(v, tl, tr);
if (l > r || tl > r || l > tr)
return node({-inf - inf, -inf, -inf, -1});
if (tl >= l && tr <= r)
return mx[v];
int tm = (tl + tr) / 2;
return getMax(l, r, v * 2, tl, tm) + getMax(l, r, v * 2 + 1, tm + 1, tr);
}
// ------------
int q;
vector < pair < int, pi > > query[MAX_N];
int ans[MAX_N];
vector < pi > st;
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1, l, r, x; i <= q; i++) {
scanf("%d%d%d", &l, &r, &x);
ans[i] = -1;
if (l == r) {
ans[i] = 1;
} else {
query[l].pb(mp(i, mp(r, x)));
}
}
buildMax();
build();
for (int i = n - 1; i > 0; i--) {
while(1) {
pi now = get(i + 1, n);
if (now.f >= a[i])
break;
update(now.s, inf);
// cout << "on at " << i << " is " << now.s << endl;
updateMax(now.s, now.s, a[now.s], 1);
}
while(!st.empty() && a[i] >= st.back().f) {
st.pp();
}
int l = i + 1, r = (st.empty() ? n : st.back().s);
updateMax(l, r, a[i], 0);
// cout << "update max " << l << ' ' << r << " with " << a[i] << endl;
st.pb(mp(a[i], i));
for (auto j : query[i]) {
node cur = getMax(i + 1, j.s.f);
// cout << i + 1 << " bw " << j.s.f << " is " << cur.maxiSum << ' ' << cur.maxiF << ' ' << cur.maxiS << endl;
ans[j.f] = (cur.maxiSum <= j.s.s);
}
}
for (int i = 1; i <= q; i++) {
assert(ans[i] != -1);
printf("%d\n", ans[i]);
}
return 0;
}
