시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 31 11 7 50.000%

문제

원주 위에 $N$개의 기둥이 있고, 각 기둥에는 $0$ 이상 $N-1$ 이하의 정수가 하나씩 쓰여 있다. 모든 정수는 정확히 한 번 쓰여 있다. $0 \leq x < y \leq N-1$인 모든 정수 $x$와 $y$에 대해, $x$가 쓰인 기둥과 $y$가 쓰인 기둥을 지면과 평행하고 높이 $x+y$만큼 공중에 떠 있는 막대로 연결하고자 한다. 물론 어떤 두 막대가 겹치면 이렇게 할 수 없으므로 실제로 막대를 놓기 전에 겹치는 막대가 있는지 알아내야 한다. 기둥은 충분히 높다고 가정하자.

입력

첫째 줄에 기둥의 개수 $N$이 주어진다.($2 \leq N \leq 1,000,000$) 다음 줄에 $0, 1, \cdots, N-1$의 순열이 주어진다.

출력

겹치는 막대가 있으면 TAK, 없으면 NIE를 출력한다.

예제 입력 1

4
0 1 2 3

예제 출력 1

NIE

예제 입력 2

4
0 1 3 2

예제 출력 2

TAK