#include <bits/stdc++.h> using namespace std; #define F first #define S second #define pb push_back //#define int long long const int N = 1e6+100; int n, q, a[N], t[N * 4], t2[N * 4]; vector < int > g[N * 4]; void build(int v, int l, int r) { if (l == r) { t[v] = a[l]; g[v] = {a[l]}; t2[v] = -1e9; // нет пары return; } int m = (l + r) >> 1; build(v<<1, l, m); build(v<<1|1, m+1, r); // слияние векторов auto &L = g[v<<1]; auto &R = g[v<<1|1]; g[v].resize(L.size() + R.size()); merge(L.begin(), L.end(), R.begin(), R.end(), g[v].begin()); t[v] = max(t[v<<1], t[v<<1|1]); t2[v] = max(t2[v<<1], t2[v<<1|1]); // ищем пару: макс слева + макс справа < него int leftMax = t[v<<1]; // бинарный поиск в правом отсортированном массиве int pos = (int)(upper_bound(R.begin(), R.end(), leftMax - 1) - R.begin()) - 1; if (pos >= 0) { t2[v] = max(t2[v], leftMax + R[pos]); } } vector < int > h; void get(int v, int l, int r, int ll, int rr){ if(ll <= l && r <= rr){ h.pb(v); return; } if(l > rr || ll > r) return; int m = (l + r) / 2; get(v + v, l, m, ll, rr); get(v + v + 1, m + 1, r, ll, rr); } void solve(){ //for (int i = 0; i < 4*N; i++) g[i].reserve(64); cin >> n >> q; for(int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n); while(q--){ int l, r, k; cin >> l >> r >> k; if(l == r){ cout << 1 << '\n'; continue; } get(1, 1, n, l, r); int ans=0, mx = t[h[0]]; for(auto to : h) ans = max(ans, t2[to]); for(int i = 1; i < h.size(); i++){ for(int j = i; j < h.size(); j++){ int ll = 0, rr = g[h[j]].size() - 1, cnt = -mx; while(ll <= rr){ int m = (ll + rr) / 2; if(mx > g[h[j]][m]){ cnt = g[h[j]][m]; ll = m + 1; } else rr = m - 1; } ans = max(ans, mx + cnt); } mx = max(mx, t[h[i]]); } if(ans <= k) cout << 1 << '\n'; else cout << 0 << '\n'; h.clear(); } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("promote.in","r",stdin); //freopen("promote.out","w",stdout); int tt=1; // cin >> tt; while(tt--){ solve(); } }