Edytor

Limit pamięci: 512 MB

Bajtazar jest programistą pracującym nad nowym, rewolucyjnym edytorem tekstu. W jego edytorze będą dostępne dwa rodzaje operacji: pierwszy to zwykła edycja tekstu, zaś drugi - cofnięcie jednej z poprzednich operacji. Nowym pomysłem Bajtazara jest wprowadzenie operacji wielopoziomowego cofania, które działa w następujący sposób:

Edycja tekstu to operacja poziomu 0. Operacja cofnięcia poziomu polega na znalezieniu oraz cofnięciu ostatnio wykonanej, nie wycofanej operacji o poziomie albo niższym. W szczególności, cofnięcie poziomu wycofuje ostatnią operację edycji tekstu, zaś cofnięcie poziomu może cofnąć zarówno edycje, jak i cofnięcia poziomu (ale nie cofnięcia wyższych poziomów).

Bardziej formalnie: każda z już wykonanych operacji może być w jednym z dwóch stanów: aktywna, albo wycofana. Niech będzie jedną z operacji. Zaraz po jej wykonaniu, jest aktywna. Jeśli jest operacją cofnięcia poziomu , znajdujemy ostatnią operację aktywną poziomu co najwyżej (oznaczmy ją ) i zmieniamy jej stan na wycofaną. Jeśli sama była operacją cofnięcia i spowodowała wycofanie innej operacji , musimy wtedy przywrócić do stanu aktywnego. Dalej postępujemy według tej samej reguły - jeśli operacja jest operacją cofnięcia i wpłynęła na stan jednej z poprzednich operacji , zmieniamy również stan operacji , oczywiście uwzględniając dalsze skutki tego faktu. Cały ten ciąg czynności kończy się, kiedy osiągniemy operację edycji tekstu.

Dla uproszczenia, całą zawartość tekstu w edytorze będziemy reprezentować przez jedną liczbę całkowitą , zwaną stanem edytora, na początku równą . Dla każdej operacji edycji znany jest stan, do którego doprowadza ona edytor. Stan edytora zależy wyłącznie od ostatniej operacji edycji będącej w stanie aktywnym. Pomóż Bajtazarowi i napisz program, który śledzi stan edytora.

Przeanalizujmy następujący przykład. Poniższa tabela zawiera kilka operacji przeprowadzonych przez Bajtazara oraz stan edytora po każdej z nich. Symbol oznacza operację edycji tekstu zmieniającą stan edytora na , zaś to operacja cofnięcia poziomu .

Operacja
Stan edytora	0	1	2	5	2	1	2	4	2	1	0	1

Na początku Bajtazar wykonał trzy operacje edycji, zmieniające stan edytora najpierw z 0 na 1, potem na 2, w końcu na 5. Potem wykonał dwie operacje cofnięcia poziomu 1 - pierwsza cofnęła operację , zaś druga cofnęła zmieniając ich stan na wycofane. W ten sposób stan edytora powrócił do 1. Kolejną operacją było cofnięcie poziomu 3, które wpłynęło na operację (przez co stała się wycofana), tym samym przywracając operację (czyniąc ją na powrót aktywną). Stan edytora przez to znowu zmienił się na 2. Operacja cofnęła operację , operacja cofnęła (wcześniej przywróconą) operację , przedostatnia operacja () cofnęła operację , zaś ostatnia operacja to , ustalająca stan edytora na 1.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą dodatnią , będącą liczbą operacji wykonanych przez Bajtazara. Kolejnych wierszy zawiera opisy operacji, po jednym w każdej linii. Opis składa się z pojedynczej liczby całkowitej (, ). Jeśli , to operacja ta jest edycją tekstu, która zmienia stan edytora na . Jeśli , to jest to operacja cofnięcia poziomu .

Możesz założyć, że dla każdej operacji cofnięcia będzie istniała wcześniejsza operacja niższego poziomu w stanie aktywnym, która będzie mogła zostać cofnięta.

Wyjście

Twój program powinien wypisać wierszy. -ty wiersz wyjścia powinien zawierać jedną liczbę całkowitą - stan edytora po wykonaniu pierwszych operacji podanych na wejściu.

Przykład

Dla danych wejściowych:

11
1
2
5
-1
-1
-3
4
-2
-1
-1
1

poprawną odpowiedzią jest:

1
2
5
2
1
2
4
2
1
0
1

Ocenianie

Podzadanie	Ograniczenia	Punkty
1		20
2	, jedynie operacje oraz	15
3	, oceniana jest wyłącznie ostatnia wypisana liczba (uwaga: pozostałe liczb wciąż muszą się zawierać między a )	28
4		37