#include <bits/stdc++.h> using namespace std; #define F first #define S second #define pb push_back const int N = 1e6 + 100; int n, q, a[N]; int 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 = upper_bound(R.begin(), R.end(), leftMax - 1) - R.begin() - 1; if (pos >= 0) t2[v] = max(t2[v], leftMax + R[pos]); } // Запрос: возвращает {максимум, лучшая пара} pair<int, int> get(int v, int l, int r, int ql, int qr) { if (qr < l || r < ql) return {-1e9, -1e9}; if (ql <= l && r <= qr) return {t[v], t2[v]}; int m = (l + r) >> 1; auto L = get(v << 1, l, m, ql, qr); auto R = get(v << 1 | 1, m + 1, r, ql, qr); int mx = max(L.first, R.first); int best = max(L.second, R.second); // если максимум слева > минимум справа if (L.first != -1e9 && R.first != -1e9) { // ищем в правом подотрезке число < L.first auto &vecR = g[v << 1 | 1]; int pos = upper_bound(vecR.begin(), vecR.end(), L.first - 1) - vecR.begin() - 1; if (pos >= 0) best = max(best, L.first + vecR[pos]); } return {mx, best}; } void solve() { 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; } auto res = get(1, 1, n, l, r); cout << (res.second <= k ? 1 : 0) << "\n"; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }