오리엔티어링

Byteman이 오리엔티어링 대회를 준비하고 있다. 참가자들은 체크포인트가 표시된 지도를 받고, 정해진 순서대로 모든 체크포인트를 한 번씩 방문해야 한다. Byteland의 전통에 따라 경로는 닫힌 고리여야 하며, 모든 체크포인트를 방문한 뒤에는 출발한 체크포인트로 되돌아온다. 적당한 장소를 찾아 경로도 정했지만, 처음이자 마지막으로 방문할 출발 지점과 진행 방향은 아직 정하지 않았다.

Byteman은 경기의 어떤 구간도 바로 앞 구간보다 더 어렵지 않기를 바란다. 그는 경로를 한 바퀴 돌면서 인접한 두 체크포인트 사이 각 구간의 난이도를 양의 정수로 기록했다. 숫자가 클수록 그 구간이 더 어렵다. 방문 순서대로 지나는 구간의 난이도가 계속 같거나 줄어들도록(증가하지 않도록) 출발 지점과 진행 방향을 고를 수 있는지 판정하여라.

첫째 줄에 경로 위 체크포인트의 개수 n (2 <= n <= 100000)이 주어진다. 체크포인트는 1번부터 n번까지 번호가 매겨져 있다. 둘째 줄에 n개의 정수 t_1, t_2, ..., t_n (1 <= t_i <= 1000000000)이 주어진다. i가 1부터 n - 1까지일 때 t_i는 체크포인트 i와 i + 1 사이 구간의 난이도이고, t_n은 체크포인트 n과 1 사이 구간의 난이도이다.

Byteman의 조건을 만족하는 출발 지점과 진행 방향이 존재하면 첫째 줄에 TAK("예"라는 뜻)를, 존재하지 않으면 NIE("아니오"라는 뜻)를 출력한다.

예를 들어 샘플 입력에서는 출발 지점을 4번 체크포인트(난이도 10인 구간의 끝)로 잡고 3번 체크포인트 방향으로 출발하면 된다. 이때 지나는 구간의 난이도는 차례로 10, 8, 3, 3, 1이 되어 증가하지 않는 조건을 만족한다. 어떤 출발 지점과 방향으로도 조건을 만족할 수 없으면 NIE를 출력한다.

샘플 입력에 대한 대회 경로. 원 안의 숫자는 체크포인트 번호이고, 간선 옆의 숫자는 각 구간의 난이도이다. 화살표는 유효한 출발 지점과 진행 방향을 나타낸다.