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