Jeongol quer guardar caixas em um depósito. Existem $N$ caixas numeradas de $1$ a $N$. A caixa $i$ ($1\le i\le N$) tem tamanho $s_i$ e capacidade $c_i$. A capacidade de cada caixa é menor que seu tamanho: $c_i<s_i$.

Como acha que tantas caixas deixam o depósito desorganizado, Jeongol quer colocar umas dentro das outras. As condições a seguir devem ser satisfeitas:

• Uma caixa pode conter outra cujo tamanho não ultrapasse sua capacidade.

• Uma caixa que já contém outra também pode ser colocada dentro de uma terceira.

• Cada caixa pode conter diretamente no máximo uma caixa. Ou seja, pode-se colocar no máximo outra caixa dentro dela, mas essa outra pode conter mais caixas.

O custo de armazenamento é a quantidade de caixas que não estão contidas em nenhuma outra.

Por exemplo, considere $N=4$ e os tamanhos e capacidades da tabela abaixo:

Se a caixa 4 for colocada na caixa 1, e a caixa 1 na caixa 3, como abaixo, duas caixas não ficam contidas em outras, portanto o custo é 2.

Porém, colocar as caixas 2 e 4 na caixa 3 como abaixo viola as condições, pois a caixa 3 contém diretamente duas caixas.

Não é obrigatório manter todas as caixas no depósito. Jeongol pretende guardar apenas algumas caixas com os menores números e descartar as demais. Ainda não decidiu quantas usar.

Ajude Jeongol escrevendo um programa que, para cada $i$ de $1$ a $N$, calcule o custo mínimo de guardar as caixas $1,2,\ldots,i$.

Restrições

• Todos os números fornecidos são inteiros.
• $2\le N\le2\times10^5$.
• $1\le c_i<s_i\le10^9$ ($1\le i\le N$).

Subtarefas

1. (7 pontos) $N\le6$.
2. (12 pontos) $s_i=c_i+1$.
3. (26 pontos) $N\le1000$.
4. (17 pontos) $s_i\le100$.
5. (38 pontos) Sem restrições adicionais.

Entrada

A primeira linha contém a quantidade de caixas $N$.

As próximas $N$ linhas, a partir da segunda, descrevem as caixas. A $i$-ésima delas contém o tamanho $s_i$ e a capacidade $c_i$ da caixa $i$, separados por um espaço.

Saída

Imprima $N$ linhas.

Na linha $i$ ($1\le i\le N$), imprima o custo mínimo de guardar as caixas $1,2,\ldots,i$.

Exemplos

Entrada 1

4
6 4
5 1
9 8
2 1

Saída 1

1
2
2
2

Entrada 2

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

Saída 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

Saída 3

1
2
3
3
3
4
4
5