Orienteering

Byteman is organizing an orienteering competition. Participants receive a map that marks checkpoints and must visit all of them in a fixed cyclic order. By the traditions of Byteland the route must be a closed loop, so after visiting every checkpoint the participants return to the checkpoint they started from. A suitable area has been found and the route has been planned, but the starting point (which is both the first and the last checkpoint to visit) and the race direction have not been chosen yet.

Byteman wants no stage of the race to be more difficult than the stage right before it. Walking the whole loop, he wrote down the difficulty of each stage between two consecutive checkpoints as a positive integer; the larger the number, the harder that stage. Decide whether a starting point and a race direction can be chosen so that the difficulties of the stages, in the order they are traversed, never increase.

The first line contains an integer n (2 <= n <= 100000), the number of checkpoints on the route. The checkpoints are numbered from 1 to n. The second line contains n integers t_1, t_2, ..., t_n (1 <= t_i <= 1000000000). For i from 1 to n - 1, t_i is the difficulty of the stage between checkpoints i and i + 1, and t_n is the difficulty of the stage between checkpoints n and 1.

Print TAK (meaning yes) on the first line if a starting point and a race direction satisfying Byteman's condition exist, and NIE (meaning no) otherwise.

For the sample input, Byteman can put the starting point at checkpoint 4 (at the end of the stage with difficulty 10) and let the competitors start toward checkpoint 3. The stages they cross then have difficulties 10, 8, 3, 3, 1, which never increase. When no starting point and direction can satisfy the condition, the answer is NIE.

The route of the competition for the sample input. The circles hold checkpoint numbers, and the numbers next to the edges are the stage difficulties. The arrows show a valid starting point and race direction.