Lollobrigida

호버크래프트 공장의 시험용 트랙은 높이가 저마다 다른 표준 블록들을 한 줄로 이어 붙여 만든다. 완벽하게 만들어진 트랙을 lollobrigida라고 부른다. lollobrigida에서는 높이가 같은 두 블록이 이웃하지 않고, 높이가 계속 커지기만 하거나 계속 작아지기만 하는 세 블록이 연속으로 놓이지도 않는다.

좀 더 정확히 말하면, 트랙에 놓인 블록들의 높이 수열을 $h_1, h_2, \ldots, h_n$이라 하자. 모든 $1 \le i \le n-2$에 대해 다음 두 조건 중 하나가 성립하면 그 트랙을 lollobrigida라고 한다.

• $h_i < h_{i+1}$ 이고 $h_{i+1} > h_{i+2}$, 또는
• $h_i > h_{i+1}$ 이고 $h_{i+1} < h_{i+2}$.

예를 들어 높이가 $3, 3, 3, 5, 2$인 블록들로는 lollobrigida를 만들 수 없다. 어떻게 배열하더라도 높이 $3$인 두 블록이 이웃하거나, $(2, 3, 5)$ 또는 $(5, 3, 2)$처럼 단조롭게 증가하거나 감소하는 세 블록이 생기기 때문이다.

반면 다른 블록 집합으로는 lollobrigida를 만들 수 있다. 예컨대 $(3, 2, 5, 2, 3, 1)$이 그러하며, 같은 집합으로 다른 lollobrigida도 만들 수 있다.

여러 개의 블록 집합이 주어진다. 각 집합마다 그 블록들을 재배열하여 lollobrigida를 만들 수 있는지 판정하여라.

첫째 줄에 데이터 집합의 개수 $d$ ($1 \le d \le 100$)가 주어진다.

이어서 $d$개의 집합이 차례로 주어진다. 각 집합의 첫째 줄에는 블록의 개수 $n$ ($3 \le n \le 1{,}000{,}000$)이 주어지고, 그 다음 $n$개의 줄에 각 블록의 높이 $h$ ($1 \le h \le 10^9$)가 한 줄에 하나씩 주어진다.

각 데이터 집합에 대해 한 줄씩, 정확히 $d$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 집합에 대한 답을 다음과 같이 출력한다.

• 그 집합으로 lollobrigida를 만들 수 있으면 TAK (폴란드어로 '예')
• 만들 수 없으면 NIE (폴란드어로 '아니오')