Skip to content

UKSPC Practice Problems » Am I sorted?

Source
driver.c, driver.cpp, or driver.java
Input
standard input
Output
standard output

We say that an array A[0..m-1] of m real numbers is k-sorted if for every i=0..m-1 such that i+k<m the following holds: A[i]<= A[i+k]. k is a positive integer. For example, an increasing sequence of any length is 1-sorted. Sequence 2,1,4,3,6,5,8,7 is 2-sorted and also 4-sorted, but not 1-sorted.

Given a sequence of n numbers your task is to find the smallest k>1 such that the sequence is k-sorted. If such k does not exist we say that the sequence is 0-sorted. Input consists of a number of lines starting with the value of m<10000 followed by m numbers, one per line. Numbers may be repeated. Output gives the smallest value of k.

Example Input

Example Output

Example Input

Example Input