#include<bits/stdc++.h> typedef int ll; #define fi first #define se second #define pii pair<ll,ll> #define N 1000006 #define LOG 18 #define endl '\n' using namespace std; bool ghuy4g; ll n, q; ll a[N], kq[N]; struct Qr { ll l, r, k, id; } qr[N]; struct Seg { ll l, r, val; } seg[N]; ll m = 0; ll st[4 * N], gh[N]; void update(ll id, ll l, ll r, ll i, ll v) { if (i > r || i < l) return; if (l == r) { st[id] = max(st[id], v); return; } ll mid = (l + r) / 2; update(id * 2, l, mid, i, v); update(id * 2 + 1, mid + 1, r, i, v); st[id] = max(st[id * 2], st[id * 2 + 1]); } ll get(ll id, ll l, ll r, ll L, ll R) { if (l > R || r < L) return 0; if (L <= l && r <= R) return st[id]; ll mid = (l + r) / 2; return max(get(id * 2, l, mid, L, R), get(id * 2 + 1, mid + 1, r, L, R)); } void pre() { vector<ll> st; for (int i = 1; i <= n; i ++) { while (st.size() && a[i] >= a[st.back()]) { st.pop_back(); } if (st.size()) { ll id = st.back(); seg[++ m] = {id, i, a[i] + a[id]}; } st.push_back(i); } sort(qr + 1, qr + 1 + q, [&](Qr A, Qr B) { return A.r < B.r; }); sort(seg + 1, seg + 1 + m, [&](Seg A, Seg B) { return A.r < B.r; }); /*for (int i = 1; i <= m; i ++) { cout << seg[i].l << " " << seg[i].r << " " << seg[i].val << endl; }*/ ll cur = 1; for (int i = 1; i <= q; i ++) { while (cur <= m && seg[cur].r <= qr[i].r) { update(1, 1, n, seg[cur].l, seg[cur].val); //cout << " upd " << seg[cur].l << " " << seg[cur].val << endl; cur ++ ; } //cout << " get " << qr[i].l << " " << qr[i].r << " " << get(1, 1, n, qr[i].l, qr[i].r) << endl; kq[qr[i].id] = get(1, 1, n, qr[i].l, qr[i].r); } for (int i = 1; i <= q; i ++) { //cout << i << " " << kq[i] << endl; cout << (kq[i] <= gh[i]) << endl; } } void sub1() { for (int i = 1; i <= q; i ++) { ll l = qr[i].l, r = qr[i].r, k = qr[i].k; ll mx = 0; for (int j = l; j <= r; j ++) { for (int z = j + 1; z <= r; z ++) { if (a[j] > a[z]) { mx = max(mx, a[j] + a[z]); } } } cout << (mx <= k) << endl; } } bool klinh; signed main() { //freopen("qcsys.inp", "r", stdin); //freopen("qcsys.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; for (int i = 1; i <= n; i ++) { cin >> a[i]; } for (int i = 1; i <= q; i ++) { cin >> qr[i].l >> qr[i].r >> qr[i].k; gh[i] = qr[i].k; qr[i].id = i; } pre(); cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024); }