Project Panoptes

Project Panoptes는 값싼 로봇 망원경으로 관측 자료를 모아 태양계 밖의 행성, 곧 외계 행성을 찾는 프로젝트다. 이 문제에서는 망원경 관측값에서 외계 행성 후보를 골라내는 간단한 프로그램을 만든다.

망원경은 별 하나의 밝기를 하루에 한 번 기록한다. 밝기가 줄어든 날은 별 앞으로 행성이 지나갔을 가능성이 있는 날이다. 밝기가 줄어든 날이 일정한 간격으로 되풀이되면 그 별은 외계 행성을 가진 후보가 된다.

관측일에 1일부터 $n$일까지 번호를 붙이고, $i$일의 밝기를 $x_i$라고 하자. 전체 평균을 $m = (x_1 + \dots + x_n) / n$이라고 할 때 $x_i < 0.8m$인 날을 어두워진 날이라고 부른다. 부등호는 엄격하다. 밝기가 평균의 80%와 정확히 같은 날은 어두워진 날이 아니다.

정수 $k$가 주기라는 것은 다음 두 조건이 모두 성립한다는 뜻이다.

• $k \ge p$
• $1 \le s \le k$이고 $s + k \le n$인 시작일 $s$가 있어서, $s, s+k, s+2k, \dots$ 중 $n$ 이하인 모든 날이 어두워진 날이다.

둘째 조건은 두 가지를 뜻한다. 주기에는 어두워진 날이 적어도 두 번 나타나야 하므로 $k$는 $n-1$을 넘지 않는다. 그리고 부분집합만으로는 부족하다. 4일, 7일, 10일이 어두워졌다고 해도 $k = 3$, $s = 1$이 주기가 되려면 1일과 13일까지 어두워져 있어야 한다.

가능한 주기 중 가장 작은 값을 구한다.

첫 줄에 정수 $n$과 $p$가 주어진다. ($2 \le n \le 1000$, $1 \le p \le n-1$) $n$은 관측 횟수, $p$는 고려할 가장 작은 주기다.

다음 $n$개의 줄에 그날의 밝기 $x$가 한 줄에 하나씩 주어진다. ($0.0 \le x \le 100.0$) 밝기는 실수이고 날짜 순서대로 주어진다.

조건을 만족하는 가장 작은 주기를 출력한다. 그런 주기가 없으면 -1을 출력한다.