Jeongol chce przechowywać pudełka w magazynie. Jest $N$ pudełek, ponumerowanych od $1$ do $N$. Pudełko $i$ ($1\le i\le N$) ma rozmiar $s_i$ i pojemność $c_i$. Każde pudełko ma pojemność mniejszą od rozmiaru: $c_i<s_i$.

Jeongol uważa, że zbyt wiele pudełek zagraca magazyn, i chce wkładać jedne w drugie. Muszą być spełnione następujące warunki:

• Pudełko może zawierać pudełko o rozmiarze nieprzekraczającym jego pojemności.

• Pudełko zawierające już inne pudełko też można włożyć do kolejnego.

• Każde pudełko może bezpośrednio zawierać najwyżej jedno pudełko. Oznacza to, że można włożyć do niego co najwyżej jedno inne pudełko, ale to inne może samo zawierać kolejne pudełka.

Koszt przechowywania to liczba pudełek niezawartych w żadnym innym pudełku.

Na przykład rozważmy $N=4$ oraz rozmiary i pojemności z poniższej tabeli:

Jeśli włożymy pudełko 4 do pudełka 1, a pudełko 1 do pudełka 3, jak poniżej, dwa pudełka nie będą zawarte w innych, więc koszt wyniesie 2.

Natomiast umieszczenie pudełek 2 i 4 w pudełku 3, jak poniżej, narusza warunki, bo pudełko 3 bezpośrednio zawiera dwa pudełka.

Nie trzeba pozostawiać wszystkich pudełek w magazynie. Jeongol zamierza zachować tylko pewną liczbę pudełek o najmniejszych numerach, a resztę wyrzucić. Nie zdecydował jeszcze, ilu pudełek użyje.

Pomóż Jeongolowi: napisz program obliczający dla każdego $i$ od $1$ do $N$ minimalny koszt przechowania pudełek $1,2,\ldots,i$.

Ograniczenia

• Wszystkie podane liczby są całkowite.
• $2\le N\le2\times10^5$.
• $1\le c_i<s_i\le10^9$ ($1\le i\le N$).

Podzadania

1. (7 punktów) $N\le6$.
2. (12 punktów) $s_i=c_i+1$.
3. (26 punktów) $N\le1000$.
4. (17 punktów) $s_i\le100$.
5. (38 punktów) Bez dodatkowych ograniczeń.

Wejście

Pierwszy wiersz zawiera liczbę pudełek $N$.

Kolejne $N$ wierszy, począwszy od drugiego, opisuje pudełka. $i$-ty z nich zawiera rozmiar $s_i$ i pojemność $c_i$ pudełka $i$, oddzielone spacją.

Wyjście

Wypisz $N$ wierszy.

W wierszu $i$ ($1\le i\le N$) wypisz minimalny koszt przechowania pudełek $1,2,\ldots,i$.

Przykład

Wejście 1

4
6 4
5 1
9 8
2 1

Wyjście 1

1
2
2
2

Wejście 2

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

Wyjście 2

1
1
2
2
2
3

Wejście 3

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

Wyjście 3

1
2
3
3
3
4
4
5