Lollobrygida

Limit pamięci: 32 MB

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 oznacza ciąg wysokości kolejnych bloków należących do toru. Jeśli dla każdego zachodzi:

• i lub
• i ,

Przykład

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

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

Zadanie

Napisz program, który wczyta ze standardowego wejścia 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ę,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita , , równa liczbie zestawów danych. W następnym wierszu standardowego wejścia zaczyna się pierwszy zestaw danych.

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

W kolejnych wierszach znajdują się wysokości bloków. Każdy z tych wierszy zawiera jedną liczbę całkowitą równą wysokości odpowiedniego bloku, .

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

Wyjście

Standardowe wyjście powinno zawierać dokładnie wierszy, po jednym dla każdego zestawu danych. W -tym wierszu standardowego wyjścia powinien być zapisany jeden wyraz:

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

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

NIE
TAK

Autor zadania: Piotr Chrząstowski-Wachtel