Problem description


Maxdiff
(C)
Limit pamięci: 256 MB
Limit czasu: 2.00 s

Jasio, tak jak wielu innych studentów takich jak on, oblał ostatnio egzamin z Algorytmów i Struktur Danych. Na egzaminie pojawiło się zadanie o przygotowaniu struktury danych, która umożliwia zarządzanie zbiorem liczb naturalnych z operacjami wstawiania elementu, usuwania elementu i obliczania tzw. mindiff’a, czyli najmniejszej różnicy między istniejącymi elementami w zbiorze.

Jasio bardzo przejął się swoją porażką i bardzo dobrze przygotował do poprawki. Okazało się, że na egzaminie poprawkowym pojawiło się bliźniaczo podobne zadanie, w którym należy utrzymywać zbiór liczb naturalnych z operacjami:

  • insert x – wstaw liczbę x do zbioru (lub zignoruj operację, jeżeli liczba x znajduje się już w zbiorze),
  • erase x – usuń liczbę x ze zbioru (lub zignoruj operację, jeżeli liczba x nie znajduje się w zbiorze),
  • maxdiff – podaj największą różnicę między elementami w zbiorze (lub zwróć 0, jeżeli moc zbioru jest mniejsza niż 2).

Jasio (może nie bez przyczyny) liczył, że zadania na egzaminie poprawkowym będą identyczne z tymi, które były na pierwszym terminie i niestety nie przygotował się na taką ewentualność i dlatego ponownie nie zaliczył egzaminu. A czy Tobie udałaby się ta sztuka?

Napisz program, który: wczyta operacje do struktury danych opisanej powyżej i wypisze odpowiedzi na wszystkie zapytania maxdiff.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę operacji. W kolejnych Q wierszach znajduje się opis kolejnych operacji, zgodnie z kolejnością ich wykonywania na strukturze danych. Opis każdej operacji składa się z jej nazwy (insert, erase lub maxdiff) oraz, w przypadku insert i erase, liczby naturalnej xi (podanej po pojedynczym odstępie w tym samym wierszu).

Wyjście

Twój program powinien wypisać odpowiedzi na wszystkie zapytania maxdiff w kolejności ich występowania (i według stanu struktury na moment występowania tych operacji).

Ograniczenia

1 ≤ Q ≤ 1 000 000, 1 ≤ xi ≤ 109.

Przykład

Wejście Wyjście
12
maxdiff
insert 7
insert 10
insert 9
maxdiff
insert 5
maxdiff
erase 10
maxdiff
erase 10
insert 5
maxdiff
0
3
5
4
4