시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 1024 MB | 64 | 26 | 20 | 46.512% |
Bajtazar opracowuje nową sztuczkę karcianą. Ma talię n kart ponumerowanych od 1 do n. Na każdej karcie chce narysować nawias otwierający lub zamykający w taki sposób, że gdy ułoży te karty po kolei, to utworzą one poprawne nawiasowanie.
Bajtazar ma dużą wprawę w tasowaniu kart i za każdym razem wychodzi mu to tak samo: po potasowaniu na i-tym miejscu znajduje się karta o numerze pi. Sztuczka ma polegać na tym, żeby po potasowaniu kart nadal tworzyły one poprawne nawiasowanie.
Dla przykładu, dla n = 6 kart i permutacji p = 4, 6, 1, 2, 3, 5 możemy nawiasy narysować tak, żeby przed potasowaniem karty tworzyły nawiasowanie (()())
, a po potasowaniu – nawiasowanie ()(())
:
Pomóż Bajtazarowi i napisz program, który dla danej permutacji p odpowie, czy da się wykonać sztuczkę, i jeśli tak, to znajdzie poprawne narysowanie nawiasów.
W pierwszym wierszu wejścia znajduje się parzysta liczba całkowita n (2 ≤ n ≤ 1 000 000) oznaczająca liczbę kart. W drugim wierszu znajduje się permutacja p1, p2, . . . , pn liczb od 1 do n.
Twój program powinien wypisać jedno słowo NIE
, jeśli nie da się narysować na kartach nawiasów tak, by spełniały wymagania zadania. W przeciwnym wypadku należy wypisać słowo złożone z n znaków (
i )
, oznaczających nawiasy, które należy narysować na kolejnych kartach. Jeśli jest więcej niż jedna poprawna odpowiedź, Twój program może wypisać dowolną z nich.
6 4 6 1 2 3 5
(()())
2 2 1
NIE