题目描述

最近，阿尔卑斯山脉（Alps）的一大片区域被划定为自然保护区。

起初，保护区内并没有狐狸。然而，多亏了持续的保护措施，保护区内的狐狸种群数量逐日恢复。每天都有一只新的狐狸到来。

生物学家 Simona 正在观察这恢复过程，她对狐狸在任何时间点形成的独特家族数量很感兴趣。Simona 知道每只狐狸 $i$ 都有一个狩猎领地，可以用线段 $[L_i, R_i]$ 表示，其中 $L_i < R_i$。这些领地可能会重叠，甚至相互包含。

根据她的研究，Simona 知道如果两只狐狸 $i$ 和 $j$ 的狩猎领地中，有一个领地嵌套在另一个领地内（即 $L_i \leq L_j < R_j \leq R_i$ 或 $L_j \leq L_i < R_i \leq R_j$），那么它们就是直接亲属关系。

两只狐狸属于同一个家族，当且仅当它们要么是直接亲属，要么通过一系列直接亲属的狐狸链相连。正式地说，两只狐狸 $a$ 和 $b$ 属于同一个家族，当且仅当存在一个狐狸序列 $c_0, c_1, \dots c_{m-1}$，使得 $a = c_0$ 且 $b = c_{m-1}$，并且对于每个 $0 \leq i < m-1$，$c_i$ 与 $c_{i+1}$ 是直属关系。

狐狸 $i$ ($0 \leq i \leq N-1$) 在第 $i$ 天到达，并从那时起一直留在保护区内，永久保持相同的狩猎领地 $[L_i, R_i]$。每只狐狸的到来可能会也可能不会改变家族关系。每天过后，Simona 都想知道狐狸 $i$ 到达后，现存的狐狸家族数量。

输入格式

输入的第一行包含一个整数 $N$，表示天数。接下来的 $N$ 行，每行包含两个整数 $L_i$ 和 $R_i$，描述狐狸 $i$ 的狩猎领地。

输出格式

输出 $N$ 行。第 $i$ 行（对于 $0 \leq i \leq N-1$）应包含一个整数，表示狐狸 $i$ 到达后存在的狐狸家族数量。

4
1 4
3 6
3 4
6 7

1
2
1
2

6
0 1
1 2
2 3
3 4
4 5
2 4

1
2
3
4
5
4

5
0 5
1 4
2 7
3 6
4 5

1
1
2
2
1

提示

样例解释

第一个样例满足子任务 1、2 和 5 的限制。第二个样例满足子任务 1、2、3 和 5 的限制。第三个样例满足子任务 1、2、4 和 5 的限制。

第一个样例。 第一只狐狸到达后，有一个家族。第二只狐狸到达后，有两个家族，因为 $[1, 4]$ 和 $[3, 6]$ 重叠但没有任何一个领地包含另一个。然后，领地为 $[3, 4]$ 的狐狸到达：它被 $[1, 4]$ 和 $[3, 6]$ 包含，所以这两个家族合并，家族数量现在为 $1$。最后，领地为 $[6, 7]$ 的狐狸没有包含任何之前的领地，也没有被包含在它们之中，因此它形成了一个新的家族，家族数量现在为 $2$。

:::align{center} :::

约束条件

• $1 \leq N \leq 100\ 000$.
• $0 \leq L_i < R_i \leq 200\ 000$.
• 对于任意两个领地，$(L_i, R_i)$ 不会重复出现。

评分方式

你的程序将在分成若干子任务的测试数据上进行测试。要获得某个子任务的分数，你必须正确解出该子任务中所有的测试数据。

• 子任务 $0$ [$0$ 分]: 样例。
• 子任务 $1$ [$10$ 分]: $N \le 100$。
• 子任务 $2$ [$15$ 分]: $N \le 2000$。
• 子任务 $3$ [$16$ 分]: $R_i - L_i \le 2$。
• 子任务 $4$ [$23$ 分]: $L_i < L_{i+1}$。
• 子任务 $5$ [$36$ 分]: 没有额外的约束条件。