#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

typedef int ll;

const ll INF = 2'000'000'000;

struct segment_tree_max {
	vector<pair<ll, ll>> tree;
	ll size;
	segment_tree_max(vector<ll> arr) {
		size = 1;
		while (size < arr.size()) {
			size *= 2;
		}
		tree.resize(size * 2, make_pair(0, 0));
		for (ll i = 0; i < arr.size(); i++) {
			tree[i + size] = make_pair(arr[i], i);
		}
		for (ll i = size - 1; i > 0; i--) {
			tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
		}
	}
	ll get(ll l, ll r) {
		return get(1, 0, size, l, r).second;
	}
	pair<ll, ll> get(ll v, ll l, ll r, ll ql, ll qr) {
		if (ql <= l && r <= qr) {
			return tree[v];
		}
		if (qr <= l || r <= ql) {
			return make_pair(0, 0);
		}
		ll mid = (l + r) / 2;
		return max(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid, r, ql, qr));
	}
};

struct segment_tree_min {
	vector<pair<ll, ll>> tree;
	ll size;
	segment_tree_min(vector<ll> arr) {
		size = 1;
		while (size < arr.size()) {
			size *= 2;
		}
		tree.resize(size * 2, make_pair(INF, INF));
		for (ll i = 0; i < arr.size(); i++) {
			tree[i + size] = make_pair(arr[i], i);
		}
		for (ll i = size - 1; i > 0; i--) {
			tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
		}
	}
	ll get(ll l, ll r) {
		return get(1, 0, size, l, r).second;
	}
	pair<ll, ll> get(ll v, ll l, ll r, ll ql, ll qr) {
		if (ql <= l && r <= qr) {
			return tree[v];
		}
		if (qr <= l || r <= ql) {
			return make_pair(INF, INF);
		}
		ll mid = (l + r) / 2;
		return min(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid, r, ql, qr));
	}
};

ll rec(ll l, ll r, ll d, ll p, ll np, segment_tree_max& stma, segment_tree_min& stmi, vector<ll>& arr, ll& num, vector<ll>& cdd, vector<ll>& pnum, vector<pair<ll, ll>>& dt) {
	if (r == l) {
		return 0;
	}
	ll now = num;
	num++;
	cdd.push_back(0);
	pnum.push_back(np);
	if (r - l == 1) {
		dt.emplace_back(p - arr[l] + 1, now);
		return arr[l] + d <= p;
	}
	ll mid = stma.get(l, r);
	ll al = rec(l, mid, d, arr[mid], now, stma, stmi, arr, num, cdd, pnum, dt);
	ll ar = rec(mid + 1, r, d, arr[mid], now, stma, stmi, arr, num, cdd, pnum, dt);
	ll ans = al + ar;
	if (al == 0) {
		cdd[now]++;
	}
	if (ar == 0) {
		cdd[now]++;
	}
	ll mi = arr[stmi.get(l, r)];
	if (mi + d <= p) {
		dt.emplace_back(p - mi + 1, now);
		ans = max(ans, 1);
	}
	return ans;
}

void make_dead(ll v, vector<ll>& pnum, vector<ll>& cdd, ll& ans) {
	ans--;
	if (pnum[v] != -1) {
		cdd[pnum[v]]++;
		if (cdd[pnum[v]] == 2) {
			ans++;
		}
	}
}

map<ll, ll> anss;

void init(ll n, vector<ll> h) {
	segment_tree_max stma(h);
	segment_tree_min stmi(h);
	vector<ll> cdd, pnum;
	vector<pair<ll, ll>> dt;
	ll num = 0;
	ll ans = rec(0, n, 0, INF, -1, stma, stmi, h, num, cdd, pnum, dt);
	sort(dt.begin(), dt.end());
	anss[0] = ans;
	for (auto[t, i] : dt) {
		make_dead(i, pnum, cdd, ans);
		anss[t] = ans;
	}
}

ll max_towers(ll l, ll r, ll d) {
	auto it = anss.lower_bound(d);
	it--;
	return it->second;
}

#ifdef LOCAL
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