Problem description

Dawno, dawno temu, za 111 górami i 111 lasami, w XIV liceum ogólnomagicznym odbywały się warsztaty przygotowujące do II etapu Bajtockiej Olimpiady Bitów i Charów. Na straży szkoły stał Hory Portier, chroniący uczniów przed nadchodzącymi potworami. Do walki z potworami wykorzystuje wyroby magiczne, oferowane mu przez Serwerusa Skype’a.

Hory Portier potrafi zaglądać w przyszłość (dzięki lekcjom z nikim innym jak jedynym Wróżbitą Maciejem), zatem ma dostępny ciąg zdarzeń, które zajdą w przyszłości. Zdarzenia ułożone są chronologicznie od 1 do N-tego. Każde ze zdarzeń jest jednego z dwóch typów:

• Do szkoły podchodzi potwór rodzaju p,
• Serwerus Skype oferuje Horemu Portierowi miksturę rodzaju p, którą Hory Portier może przyjąć lub nie.

Hory Portier doskonale zdaje sobie sprawę, że do walki z potworem rodzaju p wystarczy mu dokładnie jedna mikstura tego samego rodzaju, którą zużywa w trakcie walki. Z drugiej strony, wszystkie mikstury przechowuje w swojej Kanciapie Tajemnic, której to pojemność jest ograniczona. Nie chciałby zatem przechowywać mikstur, które mogłyby okazać się nieprzydatne. Innymi słowy, załóżmy, że w momencie, w którym Hory Portier przechowuje w swojej Kanciapie najwięcej mikstur, jest ich dokładnie K. Hory Portier chciałby, żeby wśród wszystkich możliwych strategii przyjmowania mikstur wybrać taką, że K jest możliwe najmniejsze.

Hory Portier potrafi czarować, ale nie programować, zatem poprosił Cię o pomoc! Mając listę przyszłych wydarzeń oblicz, jaki jest minimalny rozmiar Kanciapy Tajemnic, aby Hory Portier zawsze miał dostępną miksturę przed walką z potworem oraz które z mikstur powinien przyjąć od Serwerusa Skype’a.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N oznaczająca liczbę przyszłych wydarzeń. W następnych N wierszach następuje opis kolejnych zdarzeń, i-te zdarzenie opisane jest przez jeden znak oraz jedną liczbę c_i, p_i. Jeżeli c_i jest równe ! to oznacza, że Hory Portier musi w tym momencie walczyć z potworem typu p_i. Jeżeli c_i jest równe +, to oznacza, że Serwerus Skype oferuje Horemu Portierowi miksturę na potwory rodzaju p_i.

Wyjście

W pierwszym wierszu wyjścia należy wypisać jedną liczbę całkowitą K oznaczającą minimalny potrzebny rozmiar Kanciapy Tajemnic lub jedną liczbę  − 1, jeżeli niemożliwe jest wygranie ze wszystkimi potworami. Jeżeli K ≥ 0, w drugim wierszu należy wypisać ciąg liczb równych 0 lub 1, oznaczający, które z kolejnych mikstur Hory Portier przyjmuje od przez Serwerusa Skype’a według kolejności wydarzeń typu + na wejściu (0 oznacza nieprzyjęcie, a 1 przyjęcie mikstury). Jeżeli istnieje wiele możliwości, należy wpisać dowolne z nich.

Ograniczenia

1 ≤ N ≤ 200 000, 1 ≤ p_i ≤ N.

Podzadania

W każdym zestawie testowym otrzymasz 50% punktów jeżeli pierwszy wiersz wyjścia będzie poprawny.

Przykład

14
+ 2
+ 1
+ 1
+ 2
+ 4
+ 3
! 1
! 3
+ 4
! 2
+ 2
! 2
! 4
! 1

4
0 1 1 1 0 1 1 1 

3
+ 2
! 1
+ 1

-1