#include <bits/stdc++.h>

#define ll long long
#define qk(w) ((w)-1)/kc+1

using namespace std;

const int N = 2e5+11;
const ll inf = 1e18;

int n, m, kc;

ll a[N], b[N], a1[N], id[N];

struct ques {
	int l, r, k, id;
	ll ans;
} q[N];

bool cmp1(ques p1, ques p2) {
	if(qk(p1.l) != qk(p2.l)) return p1.l < p2.l;
	return p1.r < p2.r;
}
bool cmp2(ques p1, ques p2) {
	return p1.id < p2.id;
}

int ct[N], tot;

struct sgt {
	ll mx[N*4], tag[N*4];
	int siz[N*4];
	void pushdown(int k) {
		ll s = tag[k]; tag[k] = 0;
		tag[k<<1] += s; tag[k<<1|1] += s;
		mx[k<<1] += s; mx[k<<1|1] += s; 
	}
	void modify(int k, int l, int r, int L, int R, ll s) {
		if(l >= L && r <= R) {
			mx[k] += s;
			tag[k] += s;
			return;
		}
		pushdown(k);
		int mid = (l + r) >> 1; 
		if (L <= mid) modify(k<<1, l, mid, L, R, s);
		if (R > mid) modify(k<<1|1, mid+1, r, L, R, s);
		mx[k] = max(mx[k<<1], mx[k<<1|1]);
	}
	void add(int k, int l, int r, int w, int s) {
		if(l == r) {
			siz[k] += s;
			if(ct[l] == 1 && s == 1) mx[k] += inf;
			else if(ct[l] == 0 && s == -1) mx[k] -= inf;
			return;
		}
		pushdown(k);
		int mid = (l + r) >> 1;
		if (w <= mid) add(k<<1, l, mid, w, s);
		else add(k<<1|1, mid+1, r, w, s);
		siz[k] = siz[k<<1] + siz[k<<1|1];
		mx[k] = max(mx[k<<1], mx[k<<1|1]);
	}
	ll query(int k, int l, int r, int L, int R) {
		if(L > R) return -inf*2;
		if(l >= L && r <= R) return mx[k];
		pushdown(k);
		int mid = (l + r) >> 1; ll ret = -inf*2;
		if (L <= mid) ret = max(ret, query(k<<1, l, mid, L, R));
		if (R > mid) ret = max(ret, query(k<<1|1, mid+1, r, L, R));
		return ret;
	}
	int find(int k, int l, int r, int s) { 
		if (l == r) return l;
		int mid = (l+r)>>1;
		if(siz[k<<1] >= s) return find(k<<1, l, mid, s);
		return find(k<<1|1, mid+1, r, s-siz[k<<1]);
	}
} t;

void add(int w) {
	++ ct[b[w]]; tot++;
	t.add(1, 1, n, b[w], 1);
	t.modify(1, 1, n, b[w]+1, n, -a[w]);
}

void del(int w) {
	-- ct[b[w]]; tot--;
	t.add(1, 1, n, b[w], -1);
	t.modify(1, 1, n, b[w]+1, n, a[w]);
}

map <int, int> rk;

void init() {
	sort(a1+1, a1+n+1); int cnt = 0;
	for(int i = 1; i <= n; i++) {
		if(a1[i] != a1[i-1]) ++ cnt;
		rk[a1[i]] = cnt; id[cnt] = a1[i];
	}
	for(int i = 1; i <= n; i++) b[i] = rk[a[i]];
	for(int i = 1; i <= n; i++) {
		t.modify(1, 1, n, i, i, id[i]-inf);
	}
} // 离散化 

int rd() {
	int number = 0;
	char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) 
		number = number * 10 + ch - '0',
		ch = getchar();
	return number;
}

void print(ll s) {
	if (s > 9) print (s / 10);
	putchar('0' + s % 10);
}

int main() {
//	freopen("data.in","r",stdin);
//	freopen("me.out","w",stdout);
	n = rd(); m = rd();
	kc = sqrt(n);
	for (int i = 1; i <= n; i++)
		a[i] = rd(), a1[i] = a[i];
	init();
	for (int i = 1; i <= m; i++) {
		q[i].l = rd(); q[i].r = rd(); q[i].k = rd();
		q[i].id = i;
	}
	sort(q+1, q+m+1, cmp1);
	int L = 1, R = 0;
	for (int i = 1; i <= m; i++) {
		while (R < q[i].r) add(++R);
		while (R > q[i].r) del(R--);
		while (L > q[i].l) add(--L);
		while (L < q[i].l) del(L++);
		int l = 1, r = tot, ans = tot+1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			int bi = t.find(1, 1, n, mid);
			if(t.query(1, 1, n, 1, bi-(ct[bi]==1)) + q[i].k <= id[bi] &&
			t.query(1, 1, n, bi+1, n) + q[i].k <= 0) ans = mid, r = mid-1;
			else l = mid+1;
		}
		q[i].ans = tot + 1 - ans;
	}
	sort(q+1, q+m+1, cmp2);
	for (int i = 1; i <= m; i++) 
		print(q[i].ans), putchar('\n');
	return 0;
}