Sofia 是世界上最好的妻子，她总是不断想出与丈夫共度时光的新点子。 第 $i$ 个点子可以用一个区间 $[l_i, r_i]$ 来描述。这意味着 Sofia 想要参加一个从第 $l_i$ 天开始、到第 $r_i$ 天结束的活动。如果她决定参加某个活动，她必须全程参与，即从第 $l_i$ 天到第 $r_i$ 天（包含首尾）每天都在场。

Sofia 每天最多只能参加一个活动。此外，如果某个活动在第 $d$ 天结束，而另一个活动在第 $d$ 天开始，她只能参加其中一个。

每当她产生一个新的点子时，她都想知道她最多能参加多少个活动。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3 \cdot 10^5$)，表示点子的数量。 接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le 6 \cdot 10^5$)，表示第 $i$ 个点子的描述。

输出格式

对于 $1 \dots n$ 范围内的每个 $i$，输出一个整数，表示在 $1, 2, \dots, i$ 这些活动中，Sofia 最多能参加的活动数量。

样例

样例输入 1

5
1 3
3 5
1 2
5 6
4 4

样例输出 1

1
1
2
2
3