#define DEBUG 0
#if (!DEBUG)
#pragma GCC optimize("O3,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include<bits/stdc++.h>
using namespace std;
#define int long long
#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
vector<int> a;
// Persistent segment tree for point updates and range sum-like queries over versions. 0-indexed.
// Usage: PersistentSegTree<long long> pst(n);
// int root0 = pst.build(a); // or pst.build_zero();
// int root1 = pst.add(root0,pos,delta); // new version, old root0 still valid
// auto res = pst.query(root1,l,r); // sum on [l,r] in that version.
template <class T>
struct PersistentSegTree {
struct Node {
T val; int l, r;
Node(T v=T(),int _l=-1,int _r=-1): val(v),l(_l),r(_r) {}
};
int n; std::vector<Node> st;
PersistentSegTree(int _n=0): n(_n) {
if (n>0) st.reserve(20*n);
}
void init(int _n) {
n=_n; st.clear();
if (n>0) st.reserve(20*n);
}
int build_zero() { return -1; } // lazy create
template <class Vec>
int build(const Vec& a) { // a.size() must be == n
return build(0,n-1,a);
}
template <class Vec>
int build(int s,int e,const Vec& a) {
int id = (int)st.size();
st.emplace_back(T(),-1,-1);
if (s==e) {
st[id].val = (T)a[s];
} else {
int m=(s+e)>>1;
st[id].l = build(s,m,a); st[id].r = build(m+1,e,a);
pull(id);
} return id;
}
void pull(int id) {
T v=T();
if (st[id].l!=-1) v += st[st[id].l].val;
if (st[id].r!=-1) v += st[st[id].r].val;
st[id].val = v;
}
int add(int root,int pos,T delta) { // point add: a[pos] += delta
return add(root,0,n-1,pos,delta);
}
int add(int id,int s,int e,int pos,T delta) {
int cur; if (id==-1) {
cur = (int)st.size();
st.emplace_back(T(),-1,-1);
} else {
cur = (int)st.size();
st.push_back(st[id]); // clone
}
if (s==e) {
st[cur].val += delta; return cur;
}
int m=(s+e)>>1; if (pos<=m) {
int ch = (id==-1 ? -1 : st[id].l);
st[cur].l = add(ch,s,m,pos,delta);
} else {
int ch = (id==-1 ? -1 : st[id].r);
st[cur].r = add(ch,m+1,e,pos,delta);
}
pull(cur); return cur;
}
int set(int root,int pos,T v) { // point set: a[pos] = v
return set(root,0,n-1,pos,v);
}
int set(int id,int s,int e,int pos,T v) {
int cur;
if (id==-1) {
cur = (int)st.size();
st.emplace_back(T(),-1,-1);
} else {
cur = (int)st.size();
st.push_back(st[id]); // clone
}
if (s==e) {
st[cur].val = v; return cur;
}
int m=(s+e)>>1;
if (pos<=m) {
int ch = (id==-1 ? -1 : st[id].l);
st[cur].l = set(ch,s,m,pos,v);
} else {
int ch = (id==-1 ? -1 : st[id].r);
st[cur].r = set(ch,m+1,e,pos,v);
}
pull(cur); return cur;
}
T query(int root,int l,int r) const { // range sum on [l,r]
return query(root,0,n-1,l,r);
}
T query(int id,int s,int e,int l,int r) const {
if (id==-1 || r<s || e<l) return T();
if (l<=s && e<=r) return st[id].val;
int m=(s+e)>>1; T res=T();
if (l<=m) res += query(st[id].l,s,m,l,r);
if (r>m) res += query(st[id].r,m+1,e,l,r);
return res;
}
};
template <class T = int>
struct SubarrayOrderStats {
struct S {
int cnt; long long sum;
S(int c = 0, long long s = 0) : cnt(c), sum(s) {}
S& operator+=(const S& o) { cnt += o.cnt; sum += o.sum; return *this; }
};
PersistentSegTree<S> pst;
vector<T> vals;
vector<int> roots; // roots[i] = data for a[0..i-1]
int n = 0, m = 0;
SubarrayOrderStats() = default;
explicit SubarrayOrderStats(const vector<T>& a) { build(a); }
void build(const vector<T>& a) {
n = (int)a.size(); vals = a;
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
m = (int)vals.size(); pst.init(m);
roots.assign(n + 1, -1); if (m == 0) return;
roots[0] = pst.build_zero();
for (int i = 0; i < n; i++) {
int p = (int)(lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin());
roots[i + 1] = pst.add(roots[i], p, S(1, (long long)a[i]));
}
}
int countRange(int l, int r, const T& x, const T& y) const {
if (l > r || x > y || m == 0) return 0;
int L = (int)(lower_bound(vals.begin(), vals.end(), x) - vals.begin());
int R = (int)(upper_bound(vals.begin(), vals.end(), y) - vals.begin()) - 1;
if (L > R) return 0;
return pst.query(roots[r + 1], L, R).cnt - pst.query(roots[l], L, R).cnt;
}
T kthSmallest(int l, int r, int k) const {
if (l > r || m == 0) throw out_of_range("kthSmallest on empty range");
if (k < 1 || k > r - l + 1) throw out_of_range("k out of range");
int idR = roots[r + 1], idL = roots[l], s = 0, e = m - 1;
while (s < e) {
int mid = (s + e) >> 1;
int lR = (idR == -1 ? -1 : pst.st[idR].l), lL = (idL == -1 ? -1 : pst.st[idL].l);
int c = cnt(lR) - cnt(lL);
if (k <= c) idR = lR, idL = lL, e = mid;
else k -= c, idR = right(idR), idL = right(idL), s = mid + 1;
}
return vals[s];
}
long long sumSmallestK(int l, int r, int k) const {
if (l > r || m == 0) {
if (k == 0) return 0;
throw out_of_range("sumSmallestK on empty range");
}
if (k < 0 || k > r - l + 1) throw out_of_range("k out of range");
if (k == 0) return 0;
long long ans = 0;
int idR = roots[r + 1], idL = roots[l], s = 0, e = m - 1;
while (s < e && k > 0) {
int mid = (s + e) >> 1;
int lR = (idR == -1 ? -1 : pst.st[idR].l), lL = (idL == -1 ? -1 : pst.st[idL].l);
int c = cnt(lR) - cnt(lL); long long ss = sum(lR) - sum(lL);
if (k <= c) idR = lR, idL = lL, e = mid;
else ans += ss, k -= c, idR = right(idR), idL = right(idL), s = mid + 1;
}
return ans + 1LL * k * (long long)vals[s];
}
private:
int right(int id) const { return id == -1 ? -1 : pst.st[id].r; }
int cnt(int id) const { return id == -1 ? 0 : pst.st[id].val.cnt; }
long long sum(int id) const { return id == -1 ? 0LL : pst.st[id].val.sum; }
};
SubarrayOrderStats<int> *os;
inline int max_lt(int x, int y, int t) {
int l = 0, r = t;
int best = -1;
while (l <= r) {
int mid = l+(r-l)/2;
// is there some value in mid..t-1?
bool ok = os->countRange(x, y, mid, t-1) > 0;
if (ok) {
// we can increase mid
best = mid;
l = mid+1;
} else {
r = mid-1;
}
}
return best;
}
struct Seg{
struct Info {
int cost = 0;
int mx = -1;
};
int s, e,m;
Seg *l, *r;
Info info;
Info merge(const Info &l, const Info &r, int rl, int rr) {
Info c{};
c.cost = max(l.cost, r.cost);
c.mx = max(l.mx, r.mx);
if (l.mx != -1) {
// LAST in r less than l_max
// call another st
int r_max_lt = max_lt(rl, rr, l.mx);
if (r_max_lt != -1) {
c.cost = max(c.cost, l.mx + r_max_lt);
}
}
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, r->s, r->e);
} else {
info = Info{};
info.mx = a[s];
}
}
Info query(int x, int y) {
if (x <= s && e <= y) {
return info;
}
if (y < s || e < x) {
return Info{};
}
if (x > m) return r->query(x,y);
if (y < m) return l->query(x,y);
int rl = max(r->s, x);
int rr = min(r->e, y);
return merge(l->query(x,y), r->query(rl,rr), rl, rr);
}
};
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n,m;cin>>n>>m;
a.resize(n);
for (int i = 0; i < n; i++) cin>>a[i];
os = new SubarrayOrderStats(a);
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";
}
}
