Problem description

Back
Show PDF
Po prostu nawiasowanie
(popr-nawias)
Memory limit: 32 MB
Time limit: 1.00 s

Czy podane nawiasowanie jest poprawne?

Uwaga

Zbiór napisów 𝒩, które są poprawnymi nawiasowaniami definiujemy następująco:

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna dodatnia liczba całkowita N oznaczająca długość podanego napisu. W drugim wierszu znajduje się napis złożony z dokładnie N znaków, z których każdy jest albo lewym nawiasem ((), albo prawym nawiasem ()).

Wyjście

W pierwszym wierszu standardowego wyjścia należy wypisać TAK, jeżeli nawiasowanie jest poprawne, albo NIE, jeżeli nie jest.

Ograniczenia

1 ≤ N ≤ 100 000.

Przykład

Input Output 
4
()()

TAK
Input Output 
3
(()

NIE
Input Output 
6
(()))(

NIE