Mamy dany ciąg n nawiasów kwadratowych; każdy nawias może być otwierający lub zamykający. Ciąg taki jest poprawnym ciągiem nawiasów, jeśli można każdemu otwierającemu nawiasowi przyporządkować jego zamykający, tj. ciąg [][[]][] jest poprawny, ale []][ już nie.
Na danym początkowym ciągu nawiasów Jaś chce móc dokonywać następujące operacje: obrócić p-ty nawias w drugą stronę oraz swierdzić, czy w tym momencie ciąg nawiasów jest poprawnym ciągiem nawiasów. Napisz program, który mu pomoże.
W pierwszej linii wejścia jest liczba parzysta 2 <= n <= 100 000, oznaczająca liczbę nawiasów. Druga linia wejścia zawiera n liczb 1 lub -1 oddzielonych spacjami, 1 oznacza otwarcie nawiasu, -1 - zamknięcie. Kolejne linie zawierają polecenia Jasia: linia z liczbą p > 0 oznacza, że p-ty nawias należy przekręcić w drugą stronę (nawiasy są numerowane od 1); linia z liczbą 0 oznacza, że należy odpowiedzieć na pytanie czy aktualny ciąg nawiasów jest poprawny. Linia z -1 kończy dane wejściowe.
Na każde polecenie 0 (czyli zapytanie, czy ciąg jest poprawny) należy wypisać jedną linię zawierającą TAK lub NIE, w zależności od tego, czy ciąg jest poprawny.
Dla danych wejściowych
8 1 1 -1 1 1 -1 -1 -1 0 2 0 7 0 3 0 5 0 -1
prawidłową odpowiedzią jest:
TAK NIE NIE NIE TAK
[Zgłoś rozwiązanie] [Moje zgłoszenia]