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 を助け、$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$ が与えられます。

2行目から続く $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