W fabryce poduszkowców do budowy torów testowych używa się standardowych bloków o różnych wysokościach, ustawianych jeden za drugim. W idealnie zbudowanym torze, zwanym lollobrygidą, nigdy nie występują obok siebie dwa bloki jednakowej wysokości, nigdy też trzy kolejne bloki nie mają kolejno coraz większych, albo coraz mniejszych wysokości.

Mówiąc bardziej formalnie, niech h₁,...,h_n oznacza ciąg wysokości kolejnych bloków należących do toru. Jeśli dla każdego 1 <= i <= n-2 zachodzi:

• h_i < h_i+1 i h_i+1 > h_i+2 lub
• h_i > h_i+1 i h_i+1 < h_i+2,

to taki tor można nazwać lollobrygidą.

Przykład

Z zestawu 5 bloków o wysokościach 3, 3, 3, 5, 2 nie da się zbudować lollobrygidy, gdyż albo musiałyby stać w niej obok siebie dwa bloki wysokości 3, albo musi się w niej pojawić jedna z niedozwolonych sekwencji (2, 3, 5) lub (5, 3, 2).

A oto przykład lollobrygidy, poprawnie zbudowanej z innego zestawu bloków: (3, 2, 5, 2, 3, 1). Z tego zestawu można też zbudować inne lollobrygidy.

Zadanie

Napisz program, który wczyta z pliku tekstowego LOL.IN liczbę zestawów danych i dla każdego zestawu:

• wczyta liczbę bloków oraz wysokości poszczególnych bloków,
• stwierdzi, czy z podanego zestawu można zbudować lollobrygidę,
• zapisze wynik w pliku tekstowym LOL.OUT.

Wejście

W pierwszym wierszu pliku tekstowego LOL.IN znajduje się liczba całkowita d, 1 <= d <= 100, równa liczbie zestawów danych. W następnym wierszu pliku LOL.IN zaczyna się pierwszy zestaw danych.

W pierwszym wierszu każdego zestawu danych znajduje się liczba całkowita n, 3 <= n <= 1000000. Jest to liczba bloków w tym zestawie.

W kolejnych n wierszach znajdują się wysokości bloków. Każdy z tych wierszy zawiera jedną liczbę całkowitą h równą wysokości odpowiedniego bloku, 1 <= h 10^9.

Kolejne zestawy danych następują bezpośrednio po sobie.

Wyjście

Plik tekstowy LOL.OUT powinien zawierać dokładnie d wierszy, po jednym dla każdego zestawu danych. W i-tym wierszu pliku LOL.OUT powinien być zapisany jeden wyraz:

• TAK, jeżeli z i-tego zestawu bloków można zbudować lollobrygidę,
• NIE, w przeciwnym przypadku.

Przykład

Dla pliku wejściowego LOL.in:

2
5
3
3
3
5
2
6
3
3
1
5
2
2

poprawną odpowiedzią jest plik wyjściowy LOL.OUT

NIE
TAK