有一条白色直线。 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。