#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define endl '\n'
using namespace std;
const int maxn = 1e6 + 5;
const int inf = 1e18;
struct node{
int inv;
int mn, mx;
node(int in, int mn, int mx): inv(in), mn(mn), mx(mx) {}
node(){
inv = 0;
mx = 0;
mn = 0;
}
} st[4*maxn+5];
node comb(const node &a, const node &b){
// perform check if theres inversion
int inv = 0;
if (a.mx > b.mn || a.inv == 1 || b.inv == 1){
inv = 1;
}
return node(inv, min(a.mn, b.mn), max(a.mx, b.mx));
}
void build(int id, int l, int r, vector<int> &a){
if (l == r){
st[id] = node(0, a[l], a[l]);
return;
}
int mid = (l + r)/2;
build(id*2, l, mid, a);
build(id*2+1, mid+1, r, a);
st[id] = comb(st[id*2], st[id*2+1]);
}
node get(int id, int l, int r, int ul, int ur){
if (l > ur || r < ul) return node(0, inf, -inf);
if (ul <= l && r <= ur) return st[id];
int mid = (l + r)/2;
return comb(get(id*2, l, mid, ul, ur), get(id*2+1, mid+1, r, ul, ur));
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n, q, globalMn = inf;
cin >> n >> q;
vector<int> bk(n+1);
for (int i = 1; i <= n; i++){
cin >> bk[i];
globalMn = min(globalMn, bk[i]);
}
// combine sub3 into here
build(1, 1, n, bk);
for (int i = 0; i < q; i++){
int u, v, k;
cin >> u >> v >> k;
if (k >= globalMn){
for (int i = 0; i < q; i++){
// for each query determine whether the largest swap >= k or not
// sub 3, basically checking if subarray is sorted
int ok = 1;
int mx = bk[u];
for (int i = u+1; i <= v; i++){
if (bk[i] < mx && bk[i] + mx > k){
ok = 0;
break;
}
mx = max(mx, bk[i]);
}
cout << ok << endl;
}
}
else{
for (int i = 0; i < q; i++){
// for each query determine whether the largest swap >= k or not
// sub 3, basically checking if subarray is sorted
int why = get(1, 1, n, u, v).inv;
cout << 1-why << endl;
}
}
}
}I
