#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 = N, b = 317, inf = 0x3f3f3f3f; 
int n, m, a[N], l[N], r[N], x[N], rk[N], lb[B], rb[B], sr[N], cb[B], sa[N], bv[N], ans[N], ed; 
pii stk[N]; 
vector <int> dx[B], col[N]; 
deque <pii> qs[N];
set <pii> qb[B];  
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, mx = max(mx, bv[j]+ad); 
}

void solve () {
	assert(0); 
	cin >> n >> m; 
	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 <= m;i++) {
		if (rk[l[i]] == rk[r[i]]) {
			for (int j = l[i];j <= r[i];j++) {
				sa[j]++; 
				while (qs[j].size() && sa[j]+cb[rk[j]] >= qs[j].front().fi) {
					qb[rk[j]].erase({qs[j].front().fi-sa[j]+1, j}); 
					sr[qs[j].front().se] = max(sr[qs[j].front().se], i-1), qs[j].pop_front();
				}
				qs[j].pb({cb[rk[j]]+sa[j]+a[j], i}); 
				qb[rk[j]].insert({qs[j].front().fi-sa[j], j}); 
			}
		}
		else {
			for (int j = l[i];j <= rb[rk[l[i]]];j++) {
				sa[j]++; 
				while (qs[j].size() && sa[j]+cb[rk[j]] >= qs[j].front().fi) {
					qb[rk[j]].erase({qs[j].front().fi-sa[j]+1, j}); 
					sr[qs[j].front().se] = max(sr[qs[j].front().se], i-1), qs[j].pop_front();
				}
				qs[j].pb({cb[rk[j]]+sa[j]+a[j], i}); 
				qb[rk[j]].insert({qs[j].front().fi-sa[j], j}); 
			}
			for (int j = lb[rk[r[i]]];j <= r[i];j++) {
				sa[j]++; 
				while (qs[j].size() && sa[j]+cb[rk[j]] >= qs[j].front().fi) {
					qb[rk[j]].erase({qs[j].front().fi-sa[j]+1, j}); 
					sr[qs[j].front().se] = max(sr[qs[j].front().se], i-1), qs[j].pop_front();
				}
				qs[j].pb({cb[rk[j]]+sa[j]+a[j], i}); 
				qb[rk[j]].insert({qs[j].front().fi-sa[j], j}); 
			}
			for (int j = rk[l[i]]+1;j < rk[r[i]];j++) {
				cb[j]++;
				while (qb[j].size()) {
					auto k = *qb[j].begin(); 
					if (k.fi > cb[j]) break; 
					qb[j].erase(k); 
					assert(qs[k.se].size()); 
					sr[qs[k.se].front().se] = max(sr[qs[k.se].front().se], i-1); 
					qs[k.se].pop_front(); 
					if (qs[k.se].size()) qb[j].insert({qs[k.se].front().fi-sa[k.se], k.se}); 
				}
				dx[j].pb(i); 
			} 
		}
	}
	return; 
	for (int i = 1;i <= rk[n];i++) {
		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[i]) {
			while (r < j) ++r, chk(r, i, -1);  
			while (l <= j) chk(l, i, 1), l++;
			while (r < n && mx > 0) ++r, chk(r, i, -1);  
			if (mx > 0) sr[j] = max(sr[j], n); 
			else sr[j] = max(sr[j], r-1); 
		}
	}
	for (int i = 1;i <= n;i++) while (qs[i].size()) sr[qs[i].front().se] = n, qs[i].pop_front(); 
	for (int i = 1;i <= 1e5;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;
}