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