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?
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.
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.
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.
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 |
Para um conjunto de casos de teste valendo 40% dos pontos, acontece sempre que N ≤ 150.
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
1000 700 600 1200 1000 600
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)
10 INS 100 PER 1 INS 200 PER 1 INS 5000 PER 2 INS 1000 PER 1 PER 3 INS 300
100 200 200 5000 200
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