阿尔卑斯山脉的一片广阔区域最近被宣布为自然保护区。起初，保护区内没有狐狸。然而，得益于持续的保护措施，保护区内的狐狸数量一天天在恢复。每天都会有一只新的狐狸到来。生物学家 Simona 正在观察这一恢复过程，她对任何时间点狐狸所形成的互不相同的家族数量感兴趣。

Simona 知道，每只狐狸 $i$ 都有一个可以用区间 $[L_i, R_i]$ 表示的捕猎领地，其中 $L_i < R_i$。这些领地可能会重叠，甚至可能互相包含。根据她的研究，Simona 知道如果两只狐狸 $i$ 和 $j$ 的捕猎领地之一嵌套在另一个之内（即 $L_i \le L_j < R_j \le R_i$ 或 $L_j \le L_i < R_i \le R_j$），那么它们就是直接亲属。当且仅当两只狐狸是直接亲属，或者它们通过一条由直接亲属组成的链相连时，它们属于同一个家族。

狐狸 $i$ ($0 \le i \le N - 1$) 在第 $i$ 天到达，并从此留在保护区内，永远保持相同的捕猎领地 $[L_i, R_i]$。每只狐狸的到来可能会也可能不会改变家族关系。在每一天结束之后，Simona 想要知道在狐狸 $i$ 到达后狐狸家族的数量。

正式地，两只狐狸 $a$ 和 $b$ 在同一个家族中，当且仅当存在一个狐狸序列 $c_0, c_1, \dots, c_{m-1}$，使得 $a = c_0$ 且 $b = c_{m-1}$，并且对于每个 $0 \le i < m - 1$，$c_i$ 与 $c_{i+1}$ 是直接亲属。

输入格式

输入的第一行包含一个整数 $N$，表示天数。

接下来的 $N$ 行，每行包含两个整数 $L_i$ 和 $R_i$，描述狐狸 $i$ 的捕猎领地。

输出格式

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

数据范围

• $1 \le N \le 100\,000$。
• $0 \le L_i < R_i \le 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 分]：无附加限制。

样例

输入样例 1

4
1 4
3 6
3 4
6 7

输出样例 1

1
2
1
2

输入样例 2

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

输出样例 2

1
2
3
4
5
4

输入样例 3

5
0 5
1 4
2 7
3 6
4 5

输出样例 3

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。