숫자 세기 노래

아이들이 원을 이루어 서서 숫자 세기 놀이를 한다. 아이들에게는 $1$번부터 $n$번까지 번호가 매겨져 있으며, 각 $i = 1, 2, \dots, n-1$에 대해 $i+1$번 아이가 $i$번 아이의 바로 왼쪽에 서 있고, $1$번 아이는 $n$번 아이의 바로 왼쪽에 서 있다. 즉 원을 따라 왼쪽으로 갈수록 번호가 $1, 2, \dots, n$으로 커지다가 다시 $1$번으로 돌아온다.

한 번의 세기는 다음과 같이 진행된다. 매번 노래는 정확히 $k$음절로 이루어진다. 그 회차를 시작하는 아이가 첫 번째 음절을 외치고, 그 왼쪽 아이가 두 번째 음절을, 다시 그 왼쪽 아이가 세 번째 음절을 외치는 식으로 원을 따라 왼쪽으로 계속 이어진다($k$가 남은 아이 수보다 크면 같은 아이가 여러 번 외칠 수도 있다). $k$번째(마지막) 음절을 외친 아이가 지목되어 원에서 빠져나간다.

• 첫 번째 세기는 $1$번 아이가 시작한다.
• 그 다음부터는 방금 빠져나간 아이의 바로 왼쪽에 있던 아이가 새로운 세기를 시작한다.

원에 아무도 남지 않을 때까지 세기를 반복한다.

우리는 놀이 전체를 지켜보며 아이들이 빠져나간 순서를 기록했다. 이 순서만 보고 노래가 몇 음절이었는지 알아내려고 한다. 빠져나간 순서가 주어질 때, 그 순서와 정확히 일치하도록 아이들을 내보내는 $k$음절 노래가 존재하는 가장 작은 양의 정수 $k$를 구하거나, 그런 $k$가 존재하지 않음을 판정하는 프로그램을 작성하라.

첫째 줄에 정수 $n$이 주어진다($2 \le n \le 20$). 둘째 줄에는 공백으로 구분된 $n$개의 정수가 주어지며, $i$번째 수는 $i$번 아이가 몇 번째 회차에 원에서 빠져나갔는지를 나타낸다. 이 $n$개의 수는 $1$부터 $n$까지의 순열을 이룬다.

노래가 가질 수 있는 가장 작은 음절 수 $k$를 한 줄에 출력한다. 그런 $k$가 존재하지 않으면 대신 NIE를 출력한다.