← 返回题目列表

Codeforces · 926/J

J. 段

中文机器翻译题面 查看原题

有一条白色直线。 n个黑色的片段被一一添加在上面。

添加每个线段后,确定黑色线段的连通分量的数量(即黑色线段的并集中黑色线段的数量)。

特别是,如果一个线段在点 x 结束,而另一线段在点 x 开始,则这两个线段属于同一连通分量。

输入

第一行包含一个整数 n (1 ≤ n ≤ 200 000) — 段数。

接下来 n 行的第 i 行包含两个整数 li 和 ri (1 ≤ li < ri ≤ 109) — 第 i 段的左端和右端的坐标。这些段按照它们添加到白线上的顺序列出。

输出

打印 n 个整数 — 每段相加后黑色线段的连通分量数。

示例

输入 #1

3
1 3
4 5
2 4

输出 #1

1 2 1

输入 #2

9
10 20
50 60
30 40
70 80
90 100
60 70
10 40
40 50
80 90

输出 #2

1 2 3 4 5 4 3 2 1

注意

在第一个示例中,添加前两个线段后有两个分量,因为这些线段不相交。第三个添加的线段与左线段相交并在点 4 处接触右线段(根据声明,这些线段属于同一组件)。这样之后黑色线段的连通分量的数量就等于1。