Problema A - Cartas Colecionáveis

Os jogos de cartas colecionáveis, conhecidos em inglês pelas siglas TCG (Trading Card Games) ou CCG (Collectible Card Games), são famosos em todo o mundo e apaixonam jogadores e colecionadores de todos os cantos do nosso planeta. O jogo que provavelmente começou esta "loucura" foi o Magic: The Gathering, inicialmente lançado em 1993. Hoje em dia encontramos todo o tipo de cartas, de universos como Dragon Ball, Pokemon, Invizimals ou Yu-Gi-Oh.

Uma das tarefas que os colecionadores mais gostam de realizar é descobrir qual a sua k-ésima carta mais forte. Na realidade não é fácil comparar duas cartas diferentes, pois estas possuem um vasto conjunto de propriedades que podem ser mais ou menos úteis conforme o contexto. No entanto, e como simplificação, vamos assumir que uma carta pode ser classificada com um único número inteiro representando o seu valor. Assim, imagina por exemplo que tinhas 5 cartas com os seguintes valores:

1000 700 600 600 500

Se te perguntassem qual é a tua melhor carta, a resposta seria a carta de valor 1000. A 2ª melhor seria a de valor 700. Se te fosse pedida a 4ª melhor carta, a resposta seria a de valor 600 (pois é a 4ª carta em termos de valor quando as cartas estão ordenadas de forma decrescente).

Como em qualquer coleção, estão sempre a ser adicionadas e removidas cartas, fruto de novas compras ou trocas. Imagina por exemplo que era removida uma carta de valor 600 e que eram inseridas duas cartas de valores 1200 e 300, respectivamente. A coleção passaria a ter as seguintes 6 cartas, ordenadas por valor decrescente:

1200 1000 700 600 500 300

Agora a melhor carta é a de valor 1200. A 2ª melhor é a de valor 1000. A 4ª melhor continua a ser de valor 600.

E para um caso geral? Se souberes quais cartas estão a ser inseridas e removidas, consegues descobrir qual a k-ésima melhor carta?

O Problema

Dado um conjunto de N operações, que podem ser de inserção (adicionar uma carta de valor V), remoção (retirar uma carta de valor V) ou de pergunta (saber qual a K-ésima carta de maior valor) a tua tarefa é responder a todas as perguntas, indicando a respectiva carta com número de ordem K naquele momento.

Input

Na primeira linha vem um único número inteiro N, representando o número de operações.

Nas N linhas seguintes estão as operações, indicadas na ordem em que são realizadas. Cada operação é especificada por uma palavra de 3 caracteres seguida de um número inteiro e pode vir num dos seguintes 3 formatos:

No início a coleção está vazia (com zero cartas). A ordem em que surgem as operações não é conhecida à partida, mas é garantido que todas as operações são válidas, ou seja, quando estamos a remover uma carta ela existe na atual coleção e quando pedimos a K-ésima carta existem pelo menos K cartas na coleção.

Output

O output é constituído por uma linha por cada operação de pergunta. Cada uma dessas linhas, na mesma ordem das perguntas, deve conter um único número inteiro, indicando o valor da carta que está colocada na posição com a ordem indicada na respetiva pergunta.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ N ≤ 200 000       Número de operações a considerar
1 ≤ V ≤ 1 000 000       Valores das cartas

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 40% dos pontos, acontece sempre que N ≤ 150.

Exemplo de Input 1

14
INS 1000
INS 500
INS 600
INS 600
INS 700
PER 1
PER 2
PER 4
REM 600
INS 1200
INS 300
PER 1
PER 2
PER 4

Exemplo de Output 1

1000
700
600
1200
1000
600

Explicação do Input/Output 1

Corresponde ao examplo dado atrás no enunciado. Inicialmente são inseridas as 5 cartas e depois são pedidas respetivamente a melhor carta, a 2ª melhor e a 4ª melhor (que correspondem às 3 primeiras do output). Depois são feitas 2 inserções e uma remoção e são novamente pedidas a 1ª, 2ª e 4ª melhores cartas (as 3 últimas linhas do output)

Exemplo de Input 2

10
INS 100
PER 1
INS 200
PER 1
INS 5000
PER 2
INS 1000
PER 1
PER 3
INS 300

Exemplo de Output 2

100
200
200
5000
200

Explicação do Input/Output 2

100 -> 1ª  carta tem valor 100
200 100 -> 1ª carta tem valor 200
5000 200 100 -> 2ª carta tem valor 200
5000 1000 200 100 -> 1ª carta tem valor 5000
5000 1000 200 100 -> 3ª carta tem valor 200

Qualificação para a final das ONI'2014
(23/04 a 25/04 de 2014)