Medindo Bolachas

Em um evento organizado pelo NOIC, você foi chamado para organizar uma seção muito importante: os lanches! Mais especificamente, você ficou com o cargo de garantir que a bolachas não estão com tamanhos fora do padrão.

As bolachas estão sendo transportadas para dentro do evento por uma esteira, que passa por um medidor de bolachas, que consegue calcular o diâmetro da bolacha. Para garantir que não exista bolachas estranhas, você também responde $perguntas$ durante a chegada das bolachas. Para cada $pergunta$, você seleciona a bolacha $mediana$, anota seu tamanho, e a retira do grupo de bolachas. Caso o número de bolachas for par, a bolacha imediatamente maior que a mediana. Ou seja, se em um dado instante em que seja feita uma $pergunta$ tenham chego $n$ bolachas, e $n$ seja ímpar, a resposta será a $\frac{n+1}{2}$-ésima menor bolacha, e caso $n$ seja par, a resposta será a $\frac{n}{2} + 1$-ésima menor bolacha, em ambos os casos separando a bolacha do grupo (note que isso irá mudar a mediana).

Entrada:

Cada linha da entrada contém ou um inteiro $d$, indicando que uma nova bolacha de diâmetro $d$ chegou, ou um caractere $#$, indicando que uma pergunta deve ser respondida, como descrito no enunciado.

Saída

Para cada pergunta, deve-se ter uma linha de saída, contendo um inteiro, a mediana anotada em cada pergunta.

Nota:

Deve-se ler os inteiros como uma $string$, ou uma sequência de caracteres. Em $C++$, pode-se usar a função $stoi$, que recebe como parâmetro uma $string$ e retorna  número nela, ou a função $atoi$ que recebe um vetor de $char$ e retorna o número nele.

Restrições:

• Irão haver no máximo $6*10^5$ linhas de entrada
• $1 \leq d \leq 3*10^8$

Exemplos:

1
2
3
4
#
#
#
#

3
2
4
1

1
#
2
#
3
#
4
#

1
2
3
4

Para submeter sua solução, use esse link