import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.bitmanip; void main() { immutable long MAX = 10L^18+10; auto s = readln.split.map!(to!long); auto D = s[0]; auto Q = s[1]; auto rbt = redBlackTree!(Tuple!(long, long))(); long ans = 0; while (Q--) { s = readln.split.map!(to!long); auto a = s[0]; auto b = s[1]; auto lb = rbt.lowerBound(tuple(a+1, b)); auto ub = rbt.upperBound(tuple(a-1, b)); bool flag = 0; if (!lb.empty) { auto left = lb.back; if (a <= left[1] + 1) { rbt.removeKey(left); a = min(a, left[0]); b = max(b, left[1]); } } if (!ub.empty) { auto right = ub.front; if (b + 1 >= right[0]) { rbt.removeKey(right); a = min(a, right[0]); b = max(b, right[1]); } } ans = max(ans, b - a + 1); ans.writeln; rbt.insert(tuple(a, b)); } }