Problema B - Orgzl, Noxit e Izuir

A ONI é uma empresa multinacional de software responsável por grandes produtos como o Orgzl, o Noxit e o Izuir. Para criar tão excelentes productos, a ONI precisa de manter um registo de todas as tarefas que ainda estão por acabar, assim como a relação entre elas. A tua tarefa é ajudar a ONI a implementar uma ferramenta que os ajuda a organizar as suas tarefas.

A cada tarefa é associado um número de identifição (inteiro positivo), começando com a primeira tarefa de concluir o software (com número de identificação 1). Como muitas das tarefas (incluindo acabar o software!) são muito complexas, a ONI quer ser capaz de criar sub-tarefas para manter os seus engenheiros focados e organizados. Em particular, especificando um número de identificação X e um inteiro n, a ferramenta tem de adicionar n sub-tarefas à tarefa X. Para cada tarefa adicionada, o número de identificação é atribuído de forma sequencial pelo sistema (se x é for maior número de identificação usado até então, as tarefas adicionadas terão números x+1, x+2,...,x+n).

Felizmente, os engenheiros da ONI são naturalmente organizados e quando adiconam sub-tarefas a uma particular tarefa, garantem que não haverá mais adições a essa tarefa.

Ao mesmo tempo, trabalham arduamente (e produtivamente) para que as tarefas não se amontoem, e quando removem uma tarefa (por ter sido concluída), garantem que todas as suas sub-tarefas também estão concluídas e devem ser removidas. Nota que quando uma tarefa é removida o seu número de identificação nunca é reutilizado posteriormente.

Para garantir que o projecto está em bom caminho, o supervisor do projecto quer saber, sempre que há uma modificação das tarefas, quantas tarefas ainda estão por fazer.

Vejamos um exemplo:

A imagem seguinte representa esta situação

Skyline

O Problema

Dado um número Q de operações, que podem ser adições ou remoções, calcular o número total de tarefas que ainda estão por concluir no fim de cada operação.

Input

A primeira linha contém um inteiro Q que corresponde ao número de operações a considerar.

Seguem-se Q linhas, representando as operações a efetuar, no seguinte formato:

É garantido que os números de identificação X representam sempre tarefas existentes, e que uma mesma tarefa nunca será alvo de duas operações de adição.

Output

Para cada operação, uma linha contendo o número total de tarefas restantes após a operação.

Restrições

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

1 ≤ Q ≤ 100 000       Número de operações
1 ≤ n ≤ 1 000 000 000       Números de filhos adicionados numa operação

Os casos de teste deste problema estão organizados em 5 grupos com restrições adicionais diferentes:

Grupo Número de Pontos Restrições adicionais
1 10 Q ≤ 15, n ≤ 50
2 15 Q ≤ 1 000, n ≤ 1 000
3 15 A remoção de tarefas ocorre após todas as adições
4 30 n ≤ 100 000
5 30 -

Input do Exemplo 1

5
A 1 5
A 3 3
R 5
A 4 2
R 3

Output do Exemplo 1

6
9
8
10
6

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

4
A 1 3
R 4
A 2 2
R 6

Output do Exemplo 2

4
3
5
4

Prova de Seleção para as IOI'2019
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto
(9 de Junho de 2019)