Jeongol möchte Kisten in einem Lager aufbewahren. Es gibt $N$ Kisten mit Nummern von $1$ bis $N$. Kiste $i$ ($1\le i\le N$) hat Größe $s_i$ und Fassungsvermögen $c_i$. Bei jeder Kiste ist das Fassungsvermögen kleiner als die Größe: $c_i<s_i$.

Jeongol findet, dass zu viele Kisten das Lager unordentlich machen, und möchte Kisten ineinander stellen. Dabei müssen folgende Bedingungen gelten:

• Eine Kiste kann eine Kiste aufnehmen, deren Größe höchstens ihrem Fassungsvermögen entspricht.

• Eine Kiste, die bereits eine andere enthält, darf selbst in eine weitere Kiste gestellt werden.

• Jede Kiste darf höchstens eine Kiste direkt enthalten. Man darf also höchstens eine andere Kiste hineinstellen, aber diese darf ihrerseits weitere Kisten enthalten.

Die Lagerkosten entsprechen der Anzahl der Kisten, die in keiner anderen Kiste enthalten sind.

Betrachte beispielsweise $N=4$ und die Größen und Fassungsvermögen in der folgenden Tabelle:

Wird Kiste 4 in Kiste 1 und Kiste 1 in Kiste 3 gestellt, wie unten gezeigt, sind zwei Kisten in keiner anderen enthalten. Die Lagerkosten betragen somit 2.

Werden dagegen Kiste 2 und Kiste 4 wie unten in Kiste 3 gestellt, sind die Bedingungen verletzt, da Kiste 3 zwei Kisten direkt enthält.

Nicht alle Kisten müssen im Lager bleiben. Jeongol möchte nur einige Kisten mit den kleinsten Nummern behalten und die übrigen wegwerfen. Wie viele Kisten er nutzt, hat er noch nicht entschieden.

Hilf Jeongol und schreibe ein Programm, das für jedes $i$ von $1$ bis $N$ die minimalen Lagerkosten für die Kisten $1,2,\ldots,i$ berechnet.

Beschränkungen

• Alle angegebenen Zahlen sind ganzzahlig.
• $2\le N\le2\times10^5$.
• $1\le c_i<s_i\le10^9$ ($1\le i\le N$).

Teilaufgaben

1. (7 Punkte) $N\le6$.
2. (12 Punkte) $s_i=c_i+1$.
3. (26 Punkte) $N\le1000$.
4. (17 Punkte) $s_i\le100$.
5. (38 Punkte) Keine zusätzlichen Einschränkungen.

Eingabe

Die erste Zeile enthält die Anzahl der Kisten $N$.

Die nächsten $N$ Zeilen ab der zweiten beschreiben die Kisten. Die $i$-te dieser Zeilen enthält Größe $s_i$ und Fassungsvermögen $c_i$ der Kiste $i$, getrennt durch ein Leerzeichen.

Ausgabe

Gib $N$ Zeilen aus.

Gib in Zeile $i$ ($1\le i\le N$) die minimalen Lagerkosten für Kisten $1,2,\ldots,i$ aus.

Beispiele

Eingabe 1

4
6 4
5 1
9 8
2 1

Ausgabe 1

1
2
2
2

Eingabe 2

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

Ausgabe 2

1
1
2
2
2
3

Eingabe 3

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

Ausgabe 3

1
2
3
3
3
4
4
5