Problem Description

There are $n$ children numbered from $1$ to $n$ playing a circle elimination game. Child $i+1$ stands to the left of child $i$. Child $1$ stands to the left of child $n$. First, child $1$ starts counting, then the child on the left continues counting in order. Whenever the count reaches a certain number $K$, that child leaves the circle. The game ends when all children have left the circle.

Now you are given the elimination order. Find the smallest $K$.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ integers $a_i$. The $i$-th integer means that the child numbered $i$ is the $a_i$-th to leave the circle.

Output Format

Output the smallest $K$. If it does not exist, output the word NIE.

4
1 4 3 2

NIE

4
1 4 2 3

5

Hint

For $100\%$ of the testdata, $2 \le n \le 20$.

$\text{upd 2022.8.24}$: A new set of hack testdata has been added.

Translated by ChatGPT 5