8782번 - Eurozwrotnica 다국어

Czy pamiętacie pana Pawła, kolejarza z podwrocławskiej miejscowości, który był bohaterem zadania Kolejarz Paweł? W ostatnich miesiącach w jego życiu zawodowym sporo się zmieniło. Ze względu na rozbudowę infrastruktury kolejowej przed Euro 2012, na jego malutkiej stacyjce wybudowano drugi tor!

Po rozbudowie stacja pana Pawła pozostała jednokierunkowa. Składy kolejowe nadjeżdżają na stację od zachodu, i wyjeżdzają przeciwną stroną. Do pana Pawła należy podejmowanie decyzji na który tor skierować każdy z nadjeżdzających składów, i kiedy nakazać każdemu ze składów opuszczenie stacji. Na jednym torze może oczekiwać wiele składów, ale muszą opuścić stację w takiej kolejności, w której wjechały na tor (to znaczy, pociągi nie mogą wyprzedzać się na torze).

Taka budowa stacji umożliwia panu Pawłowi wpływanie na kolejność składów wyjeżdżających ze stacji. Przykładowo, jeśli na stację przyjeżdżają kolejno pociągi C, A, B, pan Paweł może skierować pierwszy z pociągów na pierwszy tor, dwa kolejne na drugi, a potem nakazać składom odjeżdżać w kolejności A, B, C.

Jutro na stację ma przyjechać N składów ponumerowanych od 1 do N. Znając kolejność, w jakiej przyjadą na stację sprawdź, czy da się tak przydzielać tory przyjeżdząjącym pociągom, żeby opuszczały stację w kolejności 1,2,...,N.

W pierwszej linii znajduje się liczba naturalna Z ( 1 <= Z <= 10 ) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

W pierwszej linii opisu pojedynczego zestawu testowego znajduje się jedna liczba naturalna N (1 <= N  <= 1000000) oznaczająca liczbę pociągów przyjeżdzających na stację. W drugiej linii opisu zestawu znajduje się N oddzielonych spacjami różnych liczb p_i ( 1 <= p_i <= N ) oznaczających numery pociągów wymienione w kolejności, w jakiej będą przyjeżdżać na stację.

Dla każdego zestawu testowego należy w osobnej linii wypisać słowo "TAK", jeśli da się ustawić pociągi w wymaganej kolejności i "NIE" w przeciwnym wypadku.