AT_abc426_c.[ABC426C] Upgrade Required

有 $N$ 个操作系统版本，按时间顺序编号为 $1,2,\dots,N$。有 $N$ 台电脑，最初第 $i$ 台电脑的操作系统版本为 $i$。

依次执行 $Q$ 次操作。第 $i$ 次操作如下：

• 将所有当前操作系统版本为 $X_i$ 或更早的电脑升级到版本 $Y_i$（且 $Y_i>X_i$）。然后，输出本次操作被升级的电脑数量。

注意，对于 $i<Q$，第 $i$ 次操作执行完成后，才会继续进行第 $i+1$ 次操作。

输入按下述格式从标准输入给出：

$N$ $Q$
$X_1$ $Y_1$
$X_2$ $Y_2$
⋮
$X_Q$ $Y_Q$

输出 $Q$ 行。
第 $i$ 行输出第 $i$ 次操作中被升级的电脑数量。

样例解释 1

本输入包含五次操作。

• 最初，8 台电脑的版本分别为 $1,2,3,4,5,6,7,8$。
• 第一次操作，将版本为 $2$ 或更早的电脑升级到版本 $6$。
  • 本次操作共升级两台，操作后各电脑版本为 $6,6,3,4,5,6,7,8$。
• 第二次操作，将版本为 $3$ 或更早的电脑升级到版本 $5$。
  • 本次操作共升级一台，操作后版本为 $6,6,5,4,5,6,7,8$。
• 第三次操作，将版本为 $1$ 或更早的电脑升级到版本 $7$。
  • 本次操作没有电脑被升级，版本保持为 $6,6,5,4,5,6,7,8$。
• 第四次操作，将版本为 $5$ 或更早的电脑升级到版本 $7$。
  • 本次操作共升级三台，版本为 $6,6,7,7,7,6,7,8$。
• 第五次操作，将版本为 $7$ 或更早的电脑升级到版本 $8$。
  • 本次操作共升级七台，全部电脑升级为 $8,8,8,8,8,8,8,8$。

数据范围

• 输入中的所有数值均为整数。
• $2 \le N \le 10^6$
• $1 \le Q \le 2 \times 10^5$
• $1 \le X_i < Y_i \le N$

由 ChatGPT 5 翻译