Eurozwrotnica

Interview

Time limit2.5sMemory limit128 MB

Summary

Decide whether the arriving train order can be split across two FIFO tracks so all trains leave in increasing order.

Level: Medium6 of 10
Topics: Queue, Greedy
Solved: No attempts yet

Problem

Do you remember Pawel the railwayman, who works at a tiny station in a town near Wroclaw? A lot has changed in his work over the past few months. Because of the railway infrastructure expansion ahead of Euro 2012, a second track was built at his little station.

Even after the expansion, the station stays one-way. Train consists arrive from the west and leave from the opposite, eastern side. Pawel decides which track to send each arriving consist to, and when to let each consist leave the station. Many consists may wait on one track, but they must leave in the same order in which they entered that track: on a single track, no consist can overtake another.

This layout lets Pawel influence the order in which consists leave the station. For example, if consists arrive in the order C, A, B, Pawel can send the first one to track 1 and the next two to track 2, and then let them leave in the order A, B, C.

Tomorrow, $N$ consists numbered from $1$ to $N$ will arrive at the station. Given the order in which they arrive, decide whether the tracks can be assigned so that the consists leave the station in the order $1, 2, \ldots, N$ .

Input

The first line contains an integer $Z$ ( $1 \le Z \le 10$ ), the number of test sets. The test sets follow one after another.

The first line of each test set contains an integer $N$ ( $1 \le N \le 10^6$ ), the number of consists arriving at the station. The second line contains $N$ distinct integers $p_i$ ( $1 \le p_i \le N$ ), separated by spaces, giving the consist numbers in the order they arrive.

Output

For each test set, print TAK on its own line if the consists can be arranged to leave in the required order, and NIE otherwise.

Examples4

Example 1
Input
```
2 
3 
1 2 3
3 
3 2 1
```
Expected output
```
TAK
NIE
```
Example 2
Input
```
1
1
1
```
Expected output
```
TAK
```
Example 3
Input
```
1
2
2 1
```
Expected output
```
TAK
```
Example 4
Input
```
1
6
4 5 6 1 2 3
```
Expected output
```
TAK
```