Jeongol veut ranger des boîtes dans un entrepôt. Il y a $N$ boîtes, numérotées de $1$ à $N$. La boîte $i$ ($1\le i\le N$) a une taille $s_i$ et une capacité $c_i$. La capacité de chaque boîte est inférieure à sa taille : $c_i<s_i$.

Trouvant que trop de boîtes encombrent l’entrepôt, Jeongol veut les placer les unes dans les autres. Les conditions suivantes doivent être respectées :

• Une boîte peut contenir une boîte dont la taille ne dépasse pas sa capacité.

• Une boîte contenant déjà une autre boîte peut elle-même être placée dans une autre.

• Chaque boîte peut contenir directement au plus une boîte. Autrement dit, on peut y placer au plus une autre boîte, mais cette dernière peut elle-même en contenir d’autres.

Le coût de stockage est le nombre de boîtes qui ne sont contenues dans aucune autre.

Par exemple, considérons $N=4$ et les tailles et capacités du tableau suivant :

Si la boîte 4 est placée dans la boîte 1, puis la boîte 1 dans la boîte 3, comme ci-dessous, deux boîtes ne sont contenues dans aucune autre et le coût vaut donc 2.

En revanche, placer les boîtes 2 et 4 dans la boîte 3 comme ci-dessous enfreint les conditions, car la boîte 3 contient directement deux boîtes.

Il n’est pas obligatoire de garder toutes les boîtes dans l’entrepôt. Jeongol prévoit de ne conserver que quelques boîtes portant les plus petits numéros et de jeter les autres. Le nombre de boîtes à utiliser n’est pas encore décidé.

Aidez Jeongol en écrivant un programme qui calcule, pour chaque $i$ de $1$ à $N$, le coût minimal de stockage des boîtes $1,2,\ldots,i$.

Contraintes

• Tous les nombres donnés sont entiers.
• $2\le N\le2\times10^5$.
• $1\le c_i<s_i\le10^9$ ($1\le i\le N$).

Sous-tâches

1. (7 points) $N\le6$.
2. (12 points) $s_i=c_i+1$.
3. (26 points) $N\le1000$.
4. (17 points) $s_i\le100$.
5. (38 points) Aucune contrainte supplémentaire.

Entrée

La première ligne contient le nombre de boîtes $N$.

Les $N$ lignes suivantes, à partir de la deuxième, décrivent les boîtes. La $i$-ième de ces lignes contient la taille $s_i$ et la capacité $c_i$ de la boîte $i$, séparées par une espace.

Sortie

Affichez $N$ lignes.

Sur la ligne $i$ ($1\le i\le N$), affichez le coût minimal de stockage des boîtes $1,2,\ldots,i$.

Exemples

Entrée 1

4
6 4
5 1
9 8
2 1

Sortie 1

1
2
2
2

Entrée 2

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

Sortie 2

1
1
2
2
2
3

Entrée 3

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

Sortie 3

1
2
3
3
3
4
4
5