Jeongol quiere guardar cajas en un almacén. Hay $N$ cajas numeradas de $1$ a $N$. La caja $i$ ($1\le i\le N$) tiene tamaño $s_i$ y capacidad $c_i$. La capacidad de cada caja es menor que su tamaño: $c_i<s_i$.

Como cree que tantas cajas desordenan el almacén, Jeongol quiere colocar unas dentro de otras. Deben cumplirse estas condiciones:

• Una caja puede contener otra cuyo tamaño no supere su capacidad.

• Una caja que ya contiene otra también puede introducirse en otra caja.

• Cada caja puede contener directamente como máximo una caja. Es decir, dentro se puede colocar como máximo otra caja, pero se permite que esta contenga más cajas.

El coste de almacenamiento es el número de cajas que no están contenidas en ninguna otra.

Por ejemplo, considera $N=4$ y los tamaños y capacidades de la tabla siguiente:

Si se coloca la caja 4 dentro de la 1 y la 1 dentro de la 3, como se muestra abajo, quedan dos cajas sin contener en otras, por lo que el coste es 2.

En cambio, colocar las cajas 2 y 4 dentro de la 3 como abajo incumple las condiciones, porque la caja 3 contiene directamente dos cajas.

No es obligatorio dejar todas las cajas en el almacén. Jeongol planea conservar solo algunas con los números más pequeños y desechar las demás. Aún no ha decidido cuántas usar.

Ayuda a Jeongol escribiendo un programa que, para cada $i$ de $1$ a $N$, calcule el coste mínimo de guardar las cajas $1,2,\ldots,i$.

Restricciones

• Todos los números dados son enteros.
• $2\le N\le2\times10^5$.
• $1\le c_i<s_i\le10^9$ ($1\le i\le N$).

Subtareas

1. (7 puntos) $N\le6$.
2. (12 puntos) $s_i=c_i+1$.
3. (26 puntos) $N\le1000$.
4. (17 puntos) $s_i\le100$.
5. (38 puntos) Sin restricciones adicionales.

Entrada

La primera línea contiene el número de cajas $N$.

Las siguientes $N$ líneas, a partir de la segunda, describen las cajas. La línea $i$ de ellas contiene el tamaño $s_i$ y la capacidad $c_i$ de la caja $i$, separados por un espacio.

Salida

Imprime $N$ líneas.

En la línea $i$ ($1\le i\le N$), imprime el coste mínimo de guardar las cajas $1,2,\ldots,i$.

Ejemplos

Entrada 1

4
6 4
5 1
9 8
2 1

Salida 1

1
2
2
2

Entrada 2

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

Salida 2

1
1
2
2
2
3

Entrada 3

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

Salida 3

1
2
3
3
3
4
4
5