AlgoLiga 2018

Klocki Jasia

Mały Jasiu, po skończonej zabawie zawsze porządkuje swoje klocki. Ponieważ samo porządkowanie jest mało interesującą czynnością dla Jasia, postanowił, że uczyni z tego rozrywkę intelektualną ustalając pewną regułę porządkowania. Klocki zawsze ustawione są w szeregu jeden za drugim i tworzą pewną n-permutację. W jednym ruchu można wziąć dowolny klocek i przestawić go o dwie pozycje na lewo, o ile jest to możliwe. W tym samym momencie dwa pozostałe klocki przesuwane są cyklicznie w prawo o jedną pozycję. Ruchy wykonujemy tak długo, aż klocki zostaną uporządkowane rosnąco według przyporządkowanych numerów. I tak oto Jasiu nudną dla niego czynność zamienił w umysłową rozrywkę. Niestety nierzadko Jasiu nie potrafi uporządkować swoich klocków i teraz zastanawia się, czy zawsze istnieje sekwencja ruchów prowadząca do uporządkowania klocków, czy też dla pewnych n-permutacji nie jest to możliwe. Pomóż małemu Jasiowi i napisz program rozstrzygający ten problem.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 1000) oznaczająca liczbę zestawów danych. Każdy zestaw opisany jest w dwóch wierszach. W pierwszym wierszu podana jest liczba n klocków Jasia (3 ≤ n ≤ 10⁵), w wierszu drugim podana jest pewna n-permutacja przedstawiająca porządek klocków Jasia po skończonej zabawie.
Pliki wejściowe nie przekraczają 3MB.

Wyjście
Dla każdego zestawu należy wypisać słowo TAK albo NIE w zależności od tego, czy jest możliwe uporządkowanie klocków w porządku rosnącym, według reguł podanych przez Jasia.

Przykład

Wejście
3
4
1 2 3 4
5
2 5 3 4 1
5
2 3 5 4 1

Wyjście
TAK
TAK
NIE