#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int MaxN = 100000;
constexpr int LogN = 16;
constexpr int Inf = 1E9;
namespace RMQ {
int st[LogN + 1][MaxN];
void build(vector<int> &H) {
int N = H.size();
for (int i = 0; i < N; ++i) {
st[0][i] = H[i];
}
for (int i = 1; (1 << i) <= N; ++i) {
for (int j = 0; j + (1 << i) - 1 < N; ++j) {
st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
}
int ask(int l, int r) {
if (l > r) {
return -1;
}
int k = __lg(r - l + 1);
return max(st[k][l], st[k][r - (1 << k) + 1]);
}
}
namespace T {
int val_l[MaxN * 4], val_r[MaxN * 4];
void build(int l, int r, int x, const vector<int> &vl, const vector<int> &vr) {
if (l == r) {
val_l[x] = vl[l];
val_r[x] = vr[l];
return;
}
int mid = (l + r) / 2;
build(l, mid, x * 2, vl, vr);
build(mid + 1, r, x * 2 + 1, vl, vr);
val_l[x] = max(val_l[x * 2], val_l[x * 2 + 1]);
val_r[x] = max(val_r[x * 2], val_r[x * 2 + 1]);
}
int find_l(int l, int r, int ql, int qr, int delta, int x) {
if (val_r[x] < delta) {
return MaxN;
}
if (l == r) {
return l;
}
int mid = (l + r) / 2;
if (ql <= l && r <= qr) {
if (val_r[x * 2] >= delta) {
return find_l(l, mid, ql, qr, delta, x * 2);
} else {
return find_l(mid + 1, r, ql, qr, delta, x * 2 + 1);
}
}
if (ql <= mid) {
int res = find_l(l, mid, ql, qr, delta, x * 2);
if (res != MaxN) {
return res;
}
}
return find_l(mid + 1, r, ql, qr, delta, x * 2 + 1);
}
int find_r(int l, int r, int ql, int qr, int delta, int x) {
if (val_l[x] < delta) {
return -1;
}
if (l == r) {
return l;
}
int mid = (l + r) / 2;
if (ql <= l && r <= qr) {
if (val_l[x * 2 + 1] >= delta) {
return find_r(mid + 1, r, ql, qr, delta, x * 2 + 1);
} else {
return find_r(l, mid, ql, qr, delta, x * 2);
}
}
if (qr > mid) {
int res = find_r(mid + 1, r, ql, qr, delta, x * 2 + 1);
if (res != -1) {
return res;
}
}
return find_r(l, mid, ql, qr, delta, x * 2);
}
}
namespace PerT {
struct Node {
int l, r;
int v;
Node() : l(), r(), v() {}
};
vector<Node> t(1);
int insert(int l, int r, int p, int x) {
int y = t.size();
t.push_back(t[x]);
++t[y].v;
if (l == r) {
return y;
}
int mid = (l + r) / 2;
if (p <= mid) {
t[y].l = insert(l, mid, p, t[x].l);
} else {
t[y].r = insert(mid + 1, r, p, t[x].r);
}
return y;
}
int ask(int l, int r, int ql, int qr, int x, int y) {
if (ql <= l && r <= qr) {
return t[y].v - t[x].v;
}
int mid = (l + r) / 2;
if (ql > mid) {
return ask(mid + 1, r, ql, qr, t[x].r, t[y].r);
} else if (qr <= mid) {
return ask(l, mid, ql, qr, t[x].l, t[y].l);
} else {
return ask(l, mid, ql, qr, t[x].l, t[y].l) + ask(mid + 1, r, ql, qr, t[x].r, t[y].r);
}
}
}
int N, root[MaxN + 1];
void init(int N_, vector<int> H) {
N = N_;
RMQ::build(H);
vector<int> stk(N + 1);
int top = 0;
vector<int> l(N), r(N);
for (int i = 0; i < N; ++i) {
while (top && H[stk[top]] > H[i]) {
--top;
}
l[i] = top ? RMQ::ask(stk[top] + 1, i - 1) : Inf;
if (top && l[i] > 0) {
l[i] -= H[i];
}
stk[++top] = i;
}
top = 0;
for (int i = N - 1; i >= 0; --i) {
while (top && H[stk[top]] > H[i]) {
--top;
}
r[i] = top ? RMQ::ask(i + 1, stk[top] - 1) : Inf;
if (top && r[i] > 0) {
r[i] -= H[i];
}
stk[++top] = i;
}
T::build(0, N - 1, 1, l, r);
for (int i = 0; i < N; ++i) {
if (l[i] == -1 || r[i] == -1) {
root[i + 1] = root[i];
continue;
}
root[i + 1] = PerT::insert(0, Inf, min(l[i], r[i]), root[i]);
}
}
int max_towers(int L, int R, int D) {
int avail_l = T::find_l(L, R, 0, N - 1, D, 1);
int avail_r = T::find_r(L, R, 0, N - 1, D, 1);
if (avail_l > avail_r || avail_r - avail_l <= 1) {
return 1;
}
return PerT::ask(0, Inf, D, Inf, root[avail_l + 1], root[avail_r]) + 2;
}
#ifdef LOCAL_GRADER
int main() {
int N, Q;
assert(2 == scanf("%d %d", &N, &Q));
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &H[i]));
}
init(N, H);
for (int i = 0; i < Q; ++i) {
int L, R, D;
assert(3 == scanf("%d %d %d", &L, &R, &D));
printf("%d\n", max_towers(L, R, D));
}
return 0;
}
#endif
