Polish version    English version  
  History of OI -> IX OI 2001/2002


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Rules
For contestants
Helpful resources
Stats
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
IX Olimpiada Informatyczna 2001/2002

Task: wyl
Author: Jakub Pawlewicz
Counting-Out Rhyme

II stage contest  

Children have gathered in a circle and are playing with a counting-out rhyme. The children are numbered 1 to n so that (for i = 1, 2, ..., n - 1) the child number i+1 stands to the left of the child number i, and the child number 1 stands to the left of the child number n. The child who is counted out in the rhyme leaves the circle. The counting out is repeated until there is no one left in the circle. The rules of the play are as follows:

  • The first counting is started by the child number 1. Each successive counting is started by the child standing to the left of the child who was last counted out.
  • Every time the rhyme consists of k syllables. The child who starts the counting out says the first syllable of the rhyme; the child standing to the left of him or her says the second syllable, the next child says the third one, and so on. The child who says the last syllable of the rhyme is counted out and leaves the circle.

example

We observe the children playing counting out and we notice the order in which they leave the circle. Basing on this information we try to guess how many syllables the counting-out rhyme consists of.

Task

Write a program which:
  • reads from the text file wyl.in the description of the order the children left the circle,
  • determines the smallest positive number k, for which the children playing with a k-syllable counting-out rhyme would leave the circle in the given order, or states that such a number k does not exist,
  • writes to the text file wyl.out the determined number k or the word NIE ("no") if such a number k does not exist.

Input

In the first line of the text file wyl.in there is one positive integer n, 2 <= n <= 20. In the second line there are n integers separated by single spaces. The i-th number tells at which turn of the counting out the child of number i left the circle.

Output

Your program should write in the first and only line of the text file wyl.out either one integer: the smallest number k of syllables that the counting-out rhyme can consist of, or one word NIE, if such a number does not exist.

Example

For the following input file wyl.in:
4
1 4 2 3
the correct answer is in the following output file wyl.out:
5



Print friendly version