#include <stdio.h>
#include <math.h>

const size_t MAXN = 2000000 + 11, MAX_N = 5010;

int n, N;
bool a[MAXN];
int b[MAXN];
int black[MAX_N];
bool change[MAX_N];

inline void Solve(int l, int r) {
	if (b[l] == b[r]) {
		if (change[b[l]]) return;
		for (; l <= r; ++l) if (!a[l])
			{ --n; --black[b[l]]; a[l] = true; }
		return;
	}
	for (; b[l] == b[l - 1]; ++l)
		if (!a[l] && !change[b[l]])
			{ --n; --black[b[l]]; a[l] = true; }
	for (; b[r] == b[r - 1]; --r)
		if (!a[r] && !change[b[r]])
			{ --n; --black[b[r]]; a[r] = true; }
	if (!a[r] && !change[b[r]])
		{ --n; --black[b[r]]; a[r] = true; }
	for (; l != r; l += N) {
		change[b[l]] = true;
		n -= black[b[l]];
		black[b[l]] = 0;
	}
}

int main() {
	freopen("axis.in", "r", stdin);
	freopen("axis.out", "w", stdout);
	int q, x, y;
	scanf("%d%d", &n, &q);
	N = ceil(sqrt((double)n));
	for (int i = 1; i <= n; ++i) {
		b[i] = ceil((double)i / N);
		++black[b[i]];
	}
	while (q--) {
		scanf("%d%d", &x, &y);
		Solve(x, y);
		printf("%d\n", n);
	}
	return 0;
}