Problema B - Escola Nacional de Informática

Na escola nacional de informática na turma olímpica há uma grande rotatividade de alunos. Inicialmente há 0 alunos na turma, mas vão entrando e saindo alunos. Cada aluno tem uma nota associada, que é um inteiro entre 1 e 10⁶ e as notas de todos os alunos em qualquer altura são distintas.

Em certos dias, o professor da turma decide dividir os alunos em grupos com pelo menos um aluno em cada. Em cada grupo, o desequilíbrio é a maior diferença de notas entre alunos desse grupo, ou seja, o valor absoluto da diferença entre a maior e menor notas. Caso o grupo só tenha um aluno então o desequilíbrio é 0. O desequilíbrio total é a soma dos desequilíbrios de todos os grupos. Sempre que o professor decidir dividir a turma, ele quer saber qual o menor desequilíbrio total para a turma atual.

Durante N dias sabemos que cada dia ou entra um aluno novo, ou sai um aluno ou o professor decide dividir os alunos em grupos. Calcula o menor desequilíbrio total para cada um dos dias em que o professor divide a turma.

Vejamos o seguinte exemplo com N = 9:

• Entra um aluno com nota 5;
• Entra um aluno com nota 1;
• Entra um aluno com nota 7;
• O professor decide dividir em 2 grupos, o ideal é: {1} e {5, 7}, que tem um desequilíbrio de 2;
• Entra um aluno com nota 2;
• Sai o aluno com nota 5;
• O professor decide dividir em 2 grupos, o ideal é: {1, 2} e {7}, que tem um desequilíbrio de 1;
• Entra um aluno com nota 3;
• O professor decide dividir em 2 grupos, o ideal é: {1, 2, 3} e {7}, que tem um desequilíbrio de 2;

O Problema

Dados N dias, em cada um uma de três coisas pode ocorrer: um novo aluno com uma nota G entra na turma; o aluno de nota G sai da turma; o professor decide dividir os alunos em K grupos e quer saber o menor desequilíbrio total.

Input

A primeira linha contém um inteiro N, que representa o número de dias. Seguem-se N linhas cada uma tem um dos seguintes formatos:

• A G, onde G é um inteiro, indicando que se juntou um aluno de nota G à turma.
• R G, onde G é um inteiro, indicando que o aluno de nota G saiu da turma.
• D K, onde K é um inteiro, indicando que o professor quer dividir a turma em K grupos.

É garantido que quando se existe sempre o aluno com nota G a remover e que nenhuns dois alunos podem ter a mesma nota. É ainda garantido que o valor de K é sempre pelo menos 1 e no máximo o número de alunos atual na turma.

Output

O output deve conter um inteiro por cada dia onde o professor decidiu dividir os alunos, representando o desequilíbrio total mínimo.

Restrições

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

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

Input do Exemplo 1

9
A 5
A 1
A 7
D 2
A 2
R 5
D 2
A 3
D 2

Output do Exemplo 1

2
1
2