/*
 * Copyright© 2024 Heratino & Nelofus. All rights reserved.
 * author: Heratino & Nelofus
 * Problem: QOJ#4780. 完美的队列
 * Tag: 分块;树状数组
 * Memory Limit: 256MB
 * Time Limit: 5000ms
 * Source: 集训队互测 2018
 * Date: 2024-03-15 
 */

// Narcissus & どうか安寧な記憶を

#include <bits/stdc++.h>
using i64 = long long;
using f64 = double;

constexpr int N = 1e5 + 10;
constexpr int N2 = 1e5;
constexpr int M = N;

bool st;
struct query {
	int l, r;
	int x;
	int t;
} Q[N];
int n, m;
int a[N];

int bl[M], br[M], pos[N];
int B, bcnt;
void blockInit() {
	B = std::ceil(sqrt((f64)n / log2(m)));
	bcnt = (n - 1) / B + 1;
	for (int i = 1; i <= bcnt; i++) {
		bl[i] = (i - 1) * B + 1;
		br[i] = i * B;
	}
	br[bcnt] = std::min(br[bcnt], n);
	for (int i = 1; i <= n; i++)
		pos[i] = (i - 1) / B + 1;
}

int maxright[N];
// 维护二元组 (x, k), 表示颜色 x 的出现次数增加了 k, k = ±1
std::vector<std::pair<int, int>> delta[N];
int seq[N];
// {{{处理整块
void solveBlock(const int &x) {
	int r = 0;
	/* 维护序列里最后一个被删掉的 */
	int tag = 0, mxval = -1e9;
	for (int i = bl[x]; i <= br[x]; i++) {
		seq[i] = a[i];
		mxval = std::max(mxval, a[i]);
	}

	static auto modify = [&](const int &p, const int &k, int &tag, int &mxval) {
		if (Q[p].r < bl[x] || Q[p].l > br[x])
			return ;

		// 每次询问的左右两个块要当作单点
		if (Q[p].l <= bl[x] && br[x] <= Q[p].r && x != pos[Q[p].l] && x != pos[Q[p].r]) {
			tag += k;
			mxval += k;
		} else {
			int mdfL = std::max(bl[x], Q[p].l), mdfR = std::min(br[x], Q[p].r);
			mxval = -1e9;
			for (int i = bl[x]; i <= br[x]; i++)
				seq[i] += tag;
			for (int i = mdfL; i <= mdfR; i++)
				seq[i] += k;
			for (int i = bl[x]; i <= br[x]; i++)
				mxval = std::max(mxval, seq[i]);
			tag = 0;
		}
	};

	for (int l = 1; l <= m; l++) {
		// 把 l 的贡献取消掉
		modify(l, 1, tag, mxval);
		while (r <= l) {
			r++;
			if (r != m + 1)
				modify(r, -1, tag, mxval);
		}
		// 如果不是整块, 那么不是这一次要处理的事
		if (Q[l].l <= bl[x] && br[x] <= Q[l].r && x != pos[Q[l].l] && x != pos[Q[l].r]) {
			while (r <= m && mxval > 0) {
				r++;
				if (r != m + 1)
					modify(r, -1, tag, mxval);
			}
			maxright[l] = std::max(maxright[l], r);
		}
	}
}
//}}}

int tr[N];
std::vector<int> single[N];
std::vector<std::pair<int, int>> smdf[N];
inline int lowbit(const int &x) {
	return x & -x;
}
inline void add(const int &x, const int &k) {
	for (int i = x; i <= m; i += lowbit(i))
		tr[i] += k;
}
inline int query(const int &x) {
	int ans = 0;
	for (int i = x; i > 0; i -= lowbit(i))
		ans += tr[i];
	return ans;
}

int cnt[N], ans;
bool ed;
/* 无法忘却的记忆与苍蓝之梦 */
int main() {
#ifdef HeratinoNelofus
	freopen("input.txt", "r", stdin);
#endif
	std::cerr << ((&ed) - (&st)) / 1048576.0 << '\n';
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> m;
	for (int i = 1; i <= n; i++)
		std::cin >> a[i];

	int K = std::__lg(m);
	blockInit();

	for (int i = 1; i <= m; i++) {
		std::cin >> Q[i].l >> Q[i].r >> Q[i].x;
		Q[i].t = i;
	}
	for (int i = 1; i <= bcnt; i++)
		solveBlock(i);

	//{{{ 提取询问编号
	for (int i = 1; i <= m; i++) {
		smdf[Q[i].l].emplace_back(i, 1);
		smdf[Q[i].r + 1].emplace_back(i, -1);
		int pl = pos[Q[i].l];
		int pr = pos[Q[i].r];

		// 在每个位置上挂上询问编号
		if (pl == pr) {
			/* 如果是同一个块, 处理自己 */
			for (int p = Q[i].l; p <= Q[i].r; p++)
				single[p].push_back(i);
		} else {
			/* 不是同一个块, 处理两端 */
			for (int p = Q[i].l; p <= br[pl]; p++)
				single[p].push_back(i);
			for (int p = bl[pr]; p <= Q[i].r; p++)
				single[p].push_back(i);
		}
	}
	//}}}

	//{{{计算每个散块询问
	for (int i = 1; i <= n; i++) {
		for (const auto &[q, k] : smdf[i])
			add(q, k);


		for (const int &x : single[i]) {
			int sum = query(x);
			int p = 0;
			int csum = 0;
			/* BIT 上倍增 */
			for (int k = K; k >= 0; k--) {
				if (p + (1 << k) <= m) {
					int t = csum + tr[p + (1 << k)];
					// 只要还能容纳
					if (t - sum <= a[i] - 1)
						csum = t, p += (1 << k);
				}
			}
			maxright[x] = std::max(maxright[x], p + 1);
		}
	}
	//}}}
	
	for (int i = 1; i <= m; i++) {
		delta[i].emplace_back(Q[i].x, 1);
		delta[maxright[i]].emplace_back(Q[i].x, -1);
	}
	for (int i = 1; i <= m; i++) {
		for (const auto &[c, k] : delta[i]) {
			if (cnt[c] == 1 && k == -1)
				ans--;
			if (cnt[c] == 0 && k ==  1)
				ans++;
			cnt[c] += k;
		}
		std::cout << ans << '\n';
	}
	return 0;
}