Problem description
Jasio uwielbia zabawy monetami. Ma ich dość dużo w swojej kolekcji. Jedną z zabaw, którą uwielbia Jasio jest wydawanie reszty swoimi monetami. W zabawie tej Jasio próbuje znaleźć dowolny sposób wydania każdej dodatniej całkowitoliczbowej kwoty, za pomocą monet ze swojej kolekcji. Interesuje go najmniejsza kwota, której nie jest w stanie wydać.
Problem w tym, że zbiór monet Jasia często się zmienia – Jasio aktywnie poszukuje i skupuje nowe monety, czasami wymienia pewne monety na inne, a czasami obdarowuje innych kolekcjonerów prezentami (oczywiście oddając im niektóre ze swoich okazów). Po każdej operacji zmiany zbioru swojej kolekcji, Jasio zastanawia się, jaka jest najmniejsza dodatnia, całkowita kwota, której nie można wydać za pomocą posiadanych monet.
Napisz program, który: wczyta operacje zmiany zbioru monet Jasia, po każdej operacji wyznaczy najmniejszą kwotę, której Jasio nie może wydać za pomocą aktualnie posiadanych monet i wypisze wyniki na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę zmian zbioru
monet Jasia. W kolejnych Q
wierszach znajdują się kolejne operacje, po jednej w wierszu. Opis
każdej operacji składa się z litery D lub U,
określającej dodanie lub usunięcie monety, pojedynczego odstępu oraz
liczby Ti
określającej wartość dodawanej/usuwanej monety.
Możesz założyć, że operacje mają sens (na przykład, że nie zdarzy się sytuacja, że jest usuwana moneta, której Jasio wcześniej nie posiadał).
Jasio może w danej chwili posiadać wiele monet o tym samym nominale. Usunięcie oznacza wtedy usunięcie jednej z nich.
Początkowo Jasio nie posiada w kolekcji żadnych monet.
Wyjście
Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć najmniejsza całkowita dodatnia kwota, której nie można wydać za pomocą monet Jasia po wykonaniu i-tej operacji (i wszystkich operacji poprzedzających).
Ograniczenia
1 ≤ Q ≤ 200 000, 1 ≤ Ti ≤ 1012.
Przykład
| Input | Output | |
|
|