Lollobrigida

A testing track in a hovercraft factory is built by joining standard blocks of different heights in a row. A perfectly built track is called a lollobrigida: in it, no two neighbouring blocks have equal height, and no three consecutive blocks have heights that only increase or only decrease.

More formally, let $h_1, h_2, \ldots, h_n$ be the sequence of block heights along a track. The track is a lollobrigida if for every $1 \le i \le n-2$ one of the following holds:

• $h_i < h_{i+1}$ and $h_{i+1} > h_{i+2}$, or
• $h_i > h_{i+1}$ and $h_{i+1} < h_{i+2}$.

For example, blocks with heights $3, 3, 3, 5, 2$ cannot form a lollobrigida: in any arrangement two blocks of height $3$ end up side by side, or one of the monotone triples $(2, 3, 5)$ or $(5, 3, 2)$ appears, and neither is allowed.

Another set of blocks, however, can form a lollobrigida, for instance $(3, 2, 5, 2, 3, 1)$; other lollobrigidas can be built from the same set as well.

You are given several sets of blocks. For each set, decide whether its blocks can be rearranged into a lollobrigida.

The first line contains the number of data sets $d$ ($1 \le d \le 100$).

The $d$ sets follow one after another. The first line of each set contains the number of blocks $n$ ($3 \le n \le 1{,}000{,}000$). Each of the next $n$ lines contains one integer $h$ ($1 \le h \le 10^9$), the height of a block.

Print exactly $d$ lines, one per data set. On the $i$-th line print the answer for the $i$-th set:

• TAK (Polish for "yes") if a lollobrigida can be built from that set,
• NIE (Polish for "no") otherwise.