/*
author: Maksim1744
created: 24.04.2024 03:13:57
*/
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
template<typename T> vector<T>& operator-- (vector<T> &v){for (auto& i : v) --i; return v;}
template<typename T> vector<T>& operator++ (vector<T> &v){for (auto& i : v) ++i; return v;}
template<typename T> istream& operator>>(istream& is, vector<T> &v){for (auto& i : v) is >> i; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator-- (pair<T, U> &p){--p.first; --p.second; return p;}
template<typename T, typename U> pair<T,U>& operator++ (pair<T, U> &p){++p.first; ++p.second; return p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second; return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U> p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}
#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun) fun
#define debugv(var) var
#define mclock void(0)
#define shows void(0)
#define debug if (false)
#define OSTREAM(...) ;
#define OSTREAM0(...) ;
#endif
template<typename T, typename F = std::function<T(const T&, const T&)>>
struct SparseTable {
vector<vector<T>> table;
vector<int> p2;
F combine;
SparseTable(int n, F combine) : combine(combine) {
while ((1 << table.size()) <= n || table.empty())
table.emplace_back(n);
}
template<typename U>
SparseTable(const vector<U>& v, F combine) : SparseTable<T>(v.size(), combine) {
table[0].assign(v.begin(), v.end());
build();
}
void build() {
p2.resize(table[0].size() + 1);
for (int i = 2; i < p2.size(); ++i)
p2[i] = p2[i / 2] + 1;
for (int i = 1; i < table.size(); ++i) {
for (int j = 0; j + (1 << i) <= table[i].size(); ++j) {
table[i][j] = combine(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}
}
}
T ask(int l, int r) {
int ln = p2[r - l + 1];
if (r - l + 1 == ln) return table[ln][l];
return combine(table[ln][l], table[ln][r - (1 << ln) + 1]);
}
};
const int inf = 2e9;
int n;
vector<int> h;
SparseTable<int> sparse_min(1, [](int a, int b) { return min(a, b); });
SparseTable<int> sparse_max(1, [](int a, int b) { return max(a, b); });
vector<int> hill, valley;
struct Node {
Node* l = nullptr;
Node* r = nullptr;
int len = 0;
int left = -1;
int last_new = -1;
Node() {}
Node(int x, int ind) {
left = x;
len = 0;
if (left != -1) {
last_new = ind;
len = 1;
}
}
int right() const {
return len % 2 == 1 ? left : 1 - left;
}
void update() {
assert(l != nullptr);
assert(r != nullptr);
if (l->len == 0) {
len = r->len;
left = r->left;
last_new = r->last_new;
} else if (r->len == 0) {
len = l->len;
left = l->left;
last_new = l->last_new;
} else {
len = l->len + r->len - (l->right() == r->left);
if (r->len == 1 && r->left == l->right()) {
last_new = l->last_new;
} else {
last_new = r->last_new;
}
left = l->left;
assert(right() == r->right());
}
}
};
OSTREAM(Node, len, left, last_new);
Node* build(int l, int r, const vector<int>& v) {
if (l == r) {
return new Node(v[l], l);
}
int m = (l + r) / 2;
auto node = new Node();
node->l = build(l, m, v);
node->r = build(m + 1, r, v);
node->update();
return node;
}
Node* update(Node* node, int i, int val, int vl, int vr) {
if (vl == vr) {
return new Node(val, i);
}
auto root = new Node();
root->l = node->l;
root->r = node->r;
int m = (vl + vr) / 2;
if (i <= m) {
root->l = update(node->l, i, val, vl, m);
} else {
root->r = update(node->r, i, val, m + 1, vr);
}
root->update();
return root;
}
Node* ask(Node* node, int l, int r, int vl, int vr) {
if (l <= vl && vr <= r) {
return node;
}
if (vr < l || vl > r) {
return new Node(-1, -1);
}
int m = (vl + vr) / 2;
Node* n = new Node();
n->l = ask(node->l, l, r, vl, m);
n->r = ask(node->r, l, r, m + 1, vr);
n->update();
return n;
}
vector<Node*> roots;
vector<int> ds;
void init(int n_, std::vector<int> h_) {
n = n_;
h = h_;
h.pb(inf);
n = h.size();
roots.clear();
ds.clear();
sparse_min = SparseTable<int>(h, [](int a, int b) { return min(a, b); });
sparse_max = SparseTable<int>(h, [](int a, int b) { return max(a, b); });
hill.assign(n, -1);
valley.assign(n, -1);
vector<int> stup, stdown;
for (int i = n - 1; i >= 0; --i) {
while (!stup.empty() && h[stup.back()] < h[i])
stup.pop_back();
while (!stdown.empty() && h[stdown.back()] > h[i])
stdown.pop_back();
if (stup.empty()) {
hill[i] = inf;
} else {
hill[i] = h[i] - sparse_min.ask(i, stup.back());
}
if (stdown.empty()) {
valley[i] = inf;
} else {
valley[i] = -h[i] + sparse_max.ask(i, stdown.back());
}
stup.push_back(i);
stdown.push_back(i);
}
vector<pair<int, int>> events;
for (int i = 0; i < n; ++i) {
if (hill[i] > 0) events.eb(hill[i], i);
if (valley[i] > 0) events.eb(valley[i], i);
}
show(hill);
show(valley);
show(events);
sort(events.begin(), events.end());
reverse(events.begin(), events.end());
ds.pb(inf + 1);
roots.pb(build(0, n-1, vector<int>(n, -1)));
int ind = 0;
while (ind < events.size()) {
shows;
int r = ind;
Node* next = roots.back();
ds.pb(events[ind].first);
show(ds.back());
while (r < events.size() && events[r].first == events[ind].first) {
int i = events[r].second;
int val = (ds.back() <= hill[i] ? 1 : (ds.back() <= valley[i] ? 0 : -1));
show(i, val);
next = update(next, i, val, 0, n-1);
++r;
}
roots.pb(next);
ind = r;
}
}
int max_towers(int l, int r, int d) {
if (l == r) return 1;
// show(hill);
// show(valley);
// int dir = -1;
// int ans = 0;
// int last = -1;
// for (int i = l; i < r; ++i) {
// if (d <= (dir == 1 ? hill[i] : valley[i])) {
// ++ans;
// last = i;
// dir = -dir;
// }
// }
// if (ans % 2 == 0 && ans > 0 && sparse_min.ask(last + 1, r) <= h[last] - d)
// ++ans;
// return max(1, (ans + 1) / 2);
int L = -1, R = ds.size();
while (R - L > 1) {
int C = (L + R) / 2;
if (ds[C] >= d)
L = C;
else
R = C;
}
show(ds);
show(L);
auto res = ask(roots[L], l, r-1, 0, n-1);
show(*roots[L]);
show(*res);
int ans = 0;
if (res->len > 0) {
ans = res->len;
if (res->left == 1) {
--ans;
}
int last = res->last_new;
if (ans % 2 == 0 && ans > 0 && sparse_min.ask(last + 1, r) <= h[last] - d)
++ans;
}
return max(1, (ans + 1) / 2);
}
#ifdef HOUSE
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, q;
cin >> n >> q;
vector<int> h(n);
cin >> h;
init(n, h);
while (q--) {
int l, r, d;
cin >> l >> r >> d;
cout << max_towers(l, r, d) << '\n';
}
return 0;
}
#endif
