#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// usage: order_of_key(x): # elements < x. find_by_order(k): k-th smallest (0-indexed)
// IMPORTANT: ordered_multiset find() doesnt work. use find_by_order(order_of_key(x)). also, lb and ub are swapped (lb returns first >x).
namespace pbds {
using namespace __gnu_pbds;
template <class K,class V> using hash_map = gp_hash_table<K,V>;
template <class K> using ordered_set = tree<K,null_type,std::less<K>,rb_tree_tag,tree_order_statistics_node_update>;
template <class K> using ordered_multiset = tree<K,null_type,std::less_equal<K>,rb_tree_tag,tree_order_statistics_node_update>;
}
#define int long long
#define DEBUG 0
#define printf if(DEBUG) printf
#define cerr if(DEBUG) cerr
template <typename T>
void print(const T& c) {
for (const auto& e : c) {
cerr << e << " ";
} cerr << '\n';
}
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << endl
#define dbg_c(v) cerr << #v << " : "; print(v)
#else
#define dbg(x)
#define dbg_c(v)
#endif
constexpr int INF = 1e9;
enum Mode {
LEFT, RIGHT
};
struct Seg{
struct Info {
int cost = 0;
int len = 0;
int max = -1; // left mode
int max_lt = -1;
string toString() const {
stringstream ss;
ss << cost << " " << len << " " << max<<" "<<max_lt;
return ss.str();
}
};
struct Info2 {
int cost = 0;
vector<int> vals;
};
int s, e,m;
Seg *l, *r;
Info2 info;
Info2 merge(const Info2 &l, const Info2 &r) {
// dbg_c(l.vals);
// dbg_c(r.vals);
Info2 c{};
c.cost = max(l.cost, r.cost);
if (!l.vals.empty()) {
int l_max = l.vals.back();
// LAST in r less than l_max
// proxy: first in r that is >= l_max with ub
// and then -1
auto it = std::lower_bound(r.vals.begin(), r.vals.end(), l_max);
if (it != r.vals.begin()) {
it--;
// printf("l_max=%d, *it=%d\n", l_max, *it);
c.cost = max(c.cost, l_max + *it);
}
}
std::merge(l.vals.begin(), l.vals.end(), r.vals.begin(), r.vals.end(), std::back_inserter(c.vals));
return c;
}
Info merge(const Info &l, const Info &r, int limit = INF) {
Info c{};
c.cost = max(l.cost, r.cost);
c.len = l.len + r.len;
if (l.len > 0) {
c.cost = max(c.cost, l.max + r.max_lt);
}
c.max = max(l.max, r.max);
if (l.max_lt < limit) c.max_lt = max(c.max_lt, l.max_lt);
if (r.max_lt < limit) c.max_lt = max(c.max_lt, r.max_lt);
cerr<<"\nl:"<<l.toString()<<"\nr:"<<r.toString()<<"\nc:"<<c.toString()<<endl;
return c;
}
Seg (int s, int e, vector<int> &a) {
this->s = s;this->e = e;
m=(s+e)/2;
if (s!=e) {
l = new Seg(s,m, a);
r = new Seg(m+1, e, a);
info = merge(l->info, r->info);
} else {
info = Info2{};
info.vals.push_back(a[s]);
}
}
Info query(int x, int y, int limit = INF) {
printf("query x=%d y=%d s=%d, e=%d\n",x,y,s,e);
if (x <= s && e <= y) {
// return info;
Info c{};
c.cost = info.cost;
// upper bound
if (!info.vals.empty()) {
c.len = info.vals.size();
c.max = info.vals.back();
auto it = std::lower_bound(info.vals.begin(), info.vals.end(), limit);
if (it != info.vals.begin()) {
it--;
c.max_lt = *it;
}
}
cerr<<"full contain c=%d: "<<c.toString()<<"\n";
return c;
}
if (y < s || e < x) {
return Info{};
}
if (x > m) return r->query(x,y, limit);
if (y < m) return l->query(x,y, limit);//mode doesnt matter here
auto li = l->query(x,y, limit);
auto ri = r->query(x,y, li.max);
auto c = merge(li, ri, limit);
return c;
}
};
signed main() {
int n,m;cin>>n>>m;
vector<int> a(n);
for (int i = 0; i < n; i++) cin>>a[i];
Seg seg(0, n-1, a);
for (int i = 0; i < m; i++) {
int l,r,k;cin>>l>>r>>k; l--,r--;
auto q = seg.query(l,r);
printf("cost %d\n",q.cost);
cout<<(q.cost <= k ? 1 : 0)<<"\n";
}
}
