Problem description

Jasio dostał w prezencie od taty zbiór odcinków o parami różnych długościach całkowitych. Zaczął wybierać z nich po trzy odcinki i budować z nich trójkąty. Trójkąty mu się jednak nie podobają. Postanowił wybrać ze swojego zbioru odcinków pewną liczbę odcinków, w taki sposób, aby nie dało się z nich skonstruować żadnego trójkąta.

Niestety, Jasio nie umie tego szybko stwierdzać, dlatego często przychodzi do taty, pokazuje mu odcinki, które sobie wybrał i pyta o liczbę odcinków, które może zachować, aby nie dało się z nich stworzyć trójkąta. Tak jak zwykle, tata nie ma czasu na takie zabawy, dlatego poprosił Cię o napisanie programu, który będzie wczytywał długości odcinków, które Jasio dokłada lub usuwa do/ze swoich rozważań i za każdym zapytaniem Jasia odpowie ile spośród rozważanych odcinków można wybrać, aby nie dało się z żadnych trzech wybranych odcinków stworzyć trójkąta.

Napisz program, który: wczyta operacje na zbiorze rozważanych odcinków oraz zapytania Jasia, wyznaczy dla każdego zapytania maksymalną liczbę odcinków, które można wybrać, aby żadne trzy nie tworzyły trójkąta i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę operacji i zapytań Jasia. W kolejnych Q wierszach znajduje się opis operacji/zapytań – po jednym w wierszu.

Opis operacji/zapytania jest w następującym formacie:

• znak +, pojedynczy odstęp oraz liczba naturalna x_i (dodanie odcinka o długości x_i do zbioru rozważanych odcinków),
• znak -, pojedynczy odstęp oraz liczba naturalna x_i (usunięcie odcinka o długości x_i ze zbioru rozważanych odcinków),
• znak Q – określający zapytanie o liczbę odcinków, które można wybrać, aby żadne dwa nie tworzyły trójkąta (dla bieżącego stanu rozważań).

Możesz założyć, że operacje są poprawne: nie nastąpi usunięcie odcinka, którego w zbiorze nie było, a także, że nigdy w zbiorze nie dodany zostanie odcinek o istniejącej już długości ze zbioru.

Wyjście

Dla każdego zapytania typu Q należy wypisać jedną liczbę całkowitą – maksymalną liczbę odcinków, które można wybrać, aby nie dało się z nich uformować trójkąta.

Ograniczenia

1 ≤ Q ≤ 200 000, 1 ≤ x_i ≤ 10¹⁸.

Przykład

9
+ 5
+ 3
+ 8
+ 7
Q
+ 1
- 8
+ 2
Q

3
4