14741번 - Impossible Design

문제

원주 위에 $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를 출력한다.

제한

힌트