Permutation

Interview

Time limit1sMemory limit128 MB

Summary

Check whether n given integers contain each number from 1 to n exactly once and print TAK or NIE.

Level: Easy3 of 10
Topics: Array, Hash map
Solved: No attempts yet

Problem

Bajtek wrote $n$ integers on a piece of paper. Determine whether they form a permutation of the numbers from $1$ to $n$ , that is, whether each of the numbers $1, 2, 3, \ldots, n-1, n$ appears exactly once in the sequence.

Input

The first line contains a single integer $n$ ( $1 \le n \le 10^6$ ), the count of numbers Bajtek wrote.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 10^9$ ) separated by spaces, where $a_i$ is the $i$ -th number in the sequence.

Output

Print TAK on the first and only line if Bajtek's sequence is a permutation of the numbers from $1$ to $n$ , or NIE otherwise.

Examples1

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