#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5+5, B = 355, b = 317, inf = 0x3f3f3f3f; 
int n, m, a[N], l[N], r[N], x[N], rk[N], lb[N], rb[N], sr[N], sa[N], bv[N], ans[N], ed; 
bool vis[N][B]; 
pii stk[N]; 
vector <int> dx, col[N]; 
vector <pii> ds[N*2]; 
deque <pii> qs[N];
int mx, ad; 

void chk (int id, int x, int k) {
	if (l[id] <= lb[x] && rb[x] <= r[id]) {
		mx += k; ad += k; 
		return; 
	}
	if (l[id] > rb[x] || r[id] < lb[x]) return; 
	mx = -inf; 
	for (int j = max(l[id], lb[x]);j <= min(r[id], rb[x]);j++) bv[j] += k; 
	for (int j = lb[x];j <= rb[x];j++) mx = max(mx, ad+bv[j]); 
}

void solve () {
	cin >> n >> m; 
	assert(n <= 5000); 
	for (int i = 1;i <= n;i++) cin >> a[i]; 
	for (int i = 1;i <= m;i++) cin >> l[i] >> r[i] >> x[i], col[x[i]].pb(i); 
	for (int i = 1; ;i++) {
		lb[i] = rb[i-1]+1; rb[i] = min(n, rb[i-1]+b);
		for (int j = lb[i];j <= rb[i];j++) rk[j] = i;  
		if (rb[i] == n) break; 
	}
	for (int i = 1;i <= rk[n];i++) {
		int cb = 0, s = 0; memset(vis, 0, sizeof vis); 
		for (int j = 0;j <= m*2;j++) ds[j].clear(); 
		for (int j = 1;j <= m;j++) {
			if (rb[i] < l[j] || lb[i] > r[j]) continue; 
			if (l[j] < lb[i] && rb[i] < r[j]) {
				++cb; 
				while (s < cb) {
					++s; 
					while (ds[s].size()) {
						auto id = ds[s].back(); ds[s].pop_back();
						if (vis[id.se][id.fi-lb[i]]) continue; 
						vis[id.se][id.fi-lb[i]] = 1; 
						sr[id.se] = max(sr[id.se], j-1), qs[id.fi].pop_front(); 
						if (qs[id.fi].size()) {
							ds[qs[id.fi].front().fi-sa[id.fi]].pb({id.fi, qs[id.fi].front().se}); 
						}
					}
				}
				continue; 
			}
			for (int z = max(lb[i], l[j]);z <= min(rb[i], r[j]);z++) {
//				vis[j][z-lb[i]] = 0; 
				sa[z]++; 
				if (qs[z].size()) {
					if (sa[z]+cb >= qs[z].front().fi) {
						vis[qs[z].front().se][z-lb[i]] = 1; 
						sr[qs[z].front().se] = max(sr[qs[z].front().se], j-1); 
						qs[z].pop_front(); 
					}
				}
				qs[z].pb({cb+sa[z]+a[z], j}); 
				s = min(s, qs[z].front().fi-sa[z]-1); 
				
				ds[qs[z].front().fi-sa[z]].pb({z, qs[z].front().se}); 
			}
		}
		for (int j = lb[i];j <= rb[i];j++) while (qs[j].size()) sr[qs[j].front().se] = m, qs[j].pop_front(); 
	}
	for (int i = 1;i <= rk[n];i++) {
		dx.clear(); 
		for (int j = 1;j <= m;j++) if (rk[l[j]] < i && i < rk[r[j]]) dx.pb(j); 
		int l = 1, r = 0; mx = -inf; ad = 0; 
		for (int z = lb[i];z <= rb[i];z++) mx = max(mx, a[z]), bv[z] = a[z]; 
		for (int j : dx) {
			while (r < j) ++r, chk(r, i, -1);  
			while (l <= j) chk(l, i, 1), l++;
			while (r < m && mx > 0) ++r, chk(r, i, -1); 
			if (mx > 0) sr[j] = max(sr[j], m); 
			else sr[j] = max(sr[j], r-1); 
		}
	}
	for (int i = 1;i <= m;i++) {
		reverse(col[i].begin(), col[i].end()); 
		for (int j : col[i]) {
			int r = sr[j];
			while (ed && stk[ed].fi <= r) {
				r = max(r, stk[ed].se); ed--; 
			}
			stk[++ed] = {j, r}; 
		}
		while (ed) {
			ans[stk[ed].fi]++; ans[stk[ed].se+1]--; 
			ed--; 
		}
	}
	for (int i = 1;i <= m;i++) ans[i] += ans[i-1]; 
	for (int i = 1;i <= m;i++) cout << ans[i] << '\n'; 
	
}

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T = 1; 
	while (T--) solve();
	return 0;
}