#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
int a[1000000];
set<int> t[4000000];
int ans[4000000];
int Max(const set<int>& x)
{
if (x.empty())
cerr << "Max got empty set as argument.";
return *x.rbegin();
}
void Build(int v, int vl, int vr)
{
if (vl == vr)
{
ans[v] = 0;
t[v].insert(a[vr]);
return;
}
int m = vl + (vr - vl) / 2;
Build(v * 2, vl, m);
Build(v * 2 + 1, m + 1, vr);
t[v].insert(t[v * 2].begin(), t[v * 2].end());
t[v].insert(t[v * 2 + 1].begin(), t[v * 2 + 1].end());
ans[v] = max(ans[v * 2], ans[v * 2 + 1]);
auto smaller = t[v * 2 + 1].lower_bound(Max(t[v * 2]));
if (smaller != t[v * 2 + 1].begin())
{
--smaller;
ans[v] = max(ans[v], Max(t[v * 2]) + *smaller);
}
}
pair<int, int> Query(int v, int vl, int vr, int l, int r, int maxAtLeft = 0)
{
// cerr << "(" << l << ", " << r << ") / (" << vl << ", " << vr << ")\n";
if (vl == l && vr == r)
{
int res = ans[v];
auto small = t[v].lower_bound(maxAtLeft);
if (small != t[v].begin())
{
--small;
res = max(res, maxAtLeft + *small);
}
// cerr << "(l = " << l << ", r = " << r << ") / " << "(vl = " << vl << ", vr = " << vr << ") returns " << res << endl;
return {res, Max(t[v])};
}
int m = vl + (vr - vl) / 2;
if (r <= m)
return Query(v * 2, vl, m, l, r, maxAtLeft);
else if (l > m)
return Query(v * 2 + 1, m + 1, vr, l, r, maxAtLeft);
pair<int, int> q1 = Query(v * 2, vl, m, l, m, maxAtLeft);
int res = q1.first;
maxAtLeft = max(maxAtLeft, q1.second);
pair<int, int> q2 = Query(v * 2 + 1, m + 1, vr, m + 1, r, maxAtLeft);
res = max(res, q2.first);
// cerr << "(l = " << l << ", r = " << r << ") / " << "(vl = " << vl << ", vr = " << vr << ") returns " << res << endl;
return {res, max(q1.second, q2.second)};
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
const int maxW = 30;
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i)
cin >> a[i];
Build(1, 0, n - 1);
while (m--)
{
int l, r, w;
/*w = rand() % (maxW + 1);
l = rand() % n;
r = rand() % n;
if (l > r) swap(l, r);*/
cin >> l >> r >> w;
--l; --r;
cerr << (Query(1, 0, n - 1, l, r).first <= w) << endl;
// cerr << l << ' ' << r << " w = " << w << endl;
// cout << (int printed = ( <= w);) << '\n';
/*int ans = 1;
for (int i = l; i <= r; ++i)
for (int j = i + 1; j <= r; ++j)
if (a[i] > a[j] && a[i] + a[j] > w)
ans = 0;
cerr << "printed: " << printed << endl;
cerr << "answer: " << ans << endl;*/
// cerr << ((ans == printed) ? "OK\n" : "WA\n");
}
}
/*
10 1
2 4 6 4 3 5 6 3 2 4
5 8 10
*/
