Jeongol 想在仓库里存放箱子。共有 $N$ 个箱子，编号为 $1$ 到 $N$。第 $i$（$1\le i\le N$）个箱子的大小为 $s_i$，容纳容量为 $c_i$。每个箱子的容量都小于其大小，即 $c_i<s_i$。

Jeongol 觉得仓库里箱子太多，显得杂乱，想把箱子放到其他箱子里面存放。必须满足以下条件：

• 一个箱子可以容纳大小不超过其容量的箱子。

• 已经装有箱子的箱子，也可以再放进其他箱子里。

• 每个箱子最多直接容纳一个箱子。也就是说，一个箱子里面最多能放另一个箱子，但允许那个箱子里面再装有其他箱子。

存放费用等于没有被装进其他箱子的箱子数量。

例如，考虑 $N=4$，四个箱子的大小和容量如下表所示：

如下图，把 4 号箱子放进 1 号箱子，再把 1 号箱子放进 3 号箱子，则有两个箱子没有被装进其他箱子，因此存放费用为 2。

但是，如下图把 2 号和 4 号箱子都放进 3 号箱子时，3 号箱子直接容纳了两个箱子，不满足条件。

不一定要把所有箱子都放在仓库里，因此 Jeongol 打算只保留编号最小的若干个箱子，丢弃其余箱子。Jeongol 尚未决定使用多少个箱子。

请帮助 Jeongol 编写程序，对于从 $1$ 到 $N$ 的每个 $i$，计算存放 $1,2,\ldots,i$ 号箱子的最小费用。

数据范围

• 给出的所有数都是整数。
• $2\le N\le2\times10^5$.
• $1\le c_i<s_i\le10^9$ ($1\le i\le N$).

子任务

1. (7 分) $N\le6$.
2. (12 分) $s_i=c_i+1$.
3. (26 分) $N\le1000$.
4. (17 分) $s_i\le100$.
5. (38 分) 无额外限制。

输入格式

第一行给出箱子数量 $N$。

从第二行起，接下来 $N$ 行给出各箱子的信息。其中第 $i$ 行给出 $i$ 号箱子的大小 $s_i$ 和容量 $c_i$，用空格分隔。

输出格式

输出 $N$ 行。

第 $i$（$1\le i\le N$）行输出存放 $1,2,\ldots,i$ 号箱子的最小费用。

样例

输入格式 1

4
6 4
5 1
9 8
2 1

输出格式 1

1
2
2
2

输入格式 2

6
3 2
5 4
3 2
4 3
4 3
3 2

输出格式 2

1
1
2
2
2
3

输入格式 3

8
13 6
7 5
9 4
11 10
4 2
15 5
16 7
8 3

输出格式 3

1
2
3
3
3
4
4
5