区间覆盖询问

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

有 $N$ 个格子从左到右排成一行，编号为 $1$ 到 $N$。初始时，所有格子都是白色。

依次处理 $Q$ 个操作。第 $i$ 个操作给出两个整数 $L_i,R_i$，把编号在 $[L_i,R_i]$ 内的所有格子染成黑色。已经是黑色的格子保持黑色。

每次操作结束后，求仍为白色的格子数量。

输入格式

第一行包含两个整数 $N,Q$。

接下来 $Q$ 行，第 $i$ 行包含两个整数 $L_i,R_i$。

输出格式

输出 $Q$ 行，第 $i$ 行表示第 $i$ 次操作后仍为白色的格子数量。

样例输入 1

10 5
3 5
8 9
5 8
2 9
6 6

样例输出 1

7
5
3
2
2

样例输入 2

1000000000 1
1 500000000

样例输出 2

500000000

数据范围

• $1\le N\le 10^9$；
• $1\le Q\le 2\times 10^5$；
• $1\le L_i\le R_i\le N$；
• 所有输入均为整数。

样例解释

第一组样例中，五次操作后白色格子数依次为 $7,5,3,2,2$。