Impossible Design

Given the circle order of a permutation of 0 to N-1, decide whether chords drawn between every pair at height x+y ever intersect.

Medium6GeometryCombinatoricsArrayNo attempts yetTime limit1sMemory limit128 MB

Description

Examples2

Problem

$N$ pillars stand on a circle. Each pillar carries one integer between $0$ and $N-1$ , and no integer is written twice.

For every pair of integers $(x, y)$ with $0 \le x < y \le N-1$ , you join the pillar that carries $x$ and the pillar that carries $y$ with one rod. The rod is parallel to the ground and floats at height $x+y$ . Assume the pillars are tall enough.

If two rods overlap, the rods cannot be placed this way. Decide whether two rods overlap before you place any of them.

Input

The first line contains the number of pillars $N$ . ( $2 \le N \le 1\,000\,000$ )

The second line contains the numbers written on the pillars, given in the order you meet them while walking around the circle in one direction. The sequence is a permutation of $0, 1, \dots, N-1$ .

Output

Print TAK if two rods overlap, and NIE otherwise.