불가능한 설계

시간 제한1초메모리 제한128 MB

요약

0부터 N-1까지의 순열이 원 위에 놓여 있을 때, 모든 쌍을 잇는 현을 서로 다른 높이로 그릴 때 두 현이 교차하는지 판정한다.

문제

원 위에 기둥 $N$ 개가 서 있다. 각 기둥에는 $0$ 이상 $N-1$ 이하의 정수가 하나씩 적혀 있고, 같은 수가 두 번 적힌 기둥은 없다.

$0 \le x < y \le N-1$ 인 모든 정수 쌍 $(x, y)$ 마다, $x$ 가 적힌 기둥과 $y$ 가 적힌 기둥을 막대 하나로 잇는다. 이 막대는 지면과 평행하고 높이 $x+y$ 에 떠 있다. 기둥은 충분히 높다고 가정한다.

막대 두 개가 겹치면 이렇게 이을 수 없다. 막대를 실제로 놓기 전에 겹치는 막대가 있는지 판정하라.

첫째 줄에 기둥의 개수 $N$ 이 주어진다. ( $2 \le N \le 1\,000\,000$ )

둘째 줄에 원을 따라 한 방향으로 읽은 순서대로 각 기둥에 적힌 수가 주어진다. 이 수열은 $0, 1, \dots, N-1$ 의 순열이다.

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