Petriukas has an array of n numbers.
In one step, Petriukas can swap two adjacent elements of the array. The number of steps is unlimited.
Is it possible for Petriukas to rearrange the array in such a way that there are no two identical elements next to each other?
Input
A natural number n and the elements of the sequence A_i (1 \le n \le 100, 1 \le A_i \le 1000).
Output
Output "TAIP" for yes or "NE" for no.
Examples
| standard input | standard output |
|---|
| 3
1 1 2
| TAIP
|
| 4
7 7 7 7
| NE
|
| 1
5
| TAIP
|