그룹 만들기

$n$명의 학생에게 $1$번부터 $n$번까지 번호가 붙어 있고, 곧 열릴 해커톤을 위해 그룹을 만들어야 한다. 당신은 캡틴인 $1$번 학생이며, 학생 $i$의 실력 수준은 $a_i$이다.

학생 $2$번부터 $n$번까지는 왼쪽에서 오른쪽으로 순서대로 한 줄로 서 있다. 당신은 두 학생 사이, 학생 $2$번의 왼쪽, 또는 학생 $n$번의 오른쪽에 설 수 있다. 나머지 $n - 1$명의 순서는 바뀌지 않는다.

또한 그룹 수 $k$를 고를 수 있다. 여기서 $k > 1$이고 $k$는 $n$의 약수이다. 그룹은 $1$번부터 $k$번까지 번호가 붙는다. 위치와 $k$를 정하면 학생들은 다음과 같이 나뉜다.

왼쪽에서 첫 번째 학생은 $1$번 그룹, 두 번째 학생은 $2$번 그룹에 들어가고, 이렇게 $k$번째 학생까지 $k$번 그룹에 들어간다. 이어서 $(k+1)$번째 학생은 다시 $1$번 그룹, $(k+2)$번째 학생은 $2$번 그룹에 들어가며, 이 규칙이 $n$번째 학생까지 반복된다.

형식적으로 쓰면, 각 $j$ ($1 \le j \le k$)와 각 $i$ ($0 \le i < n/k$)에 대해 왼쪽에서 $(i \times k + j)$번째 학생은 $j$번 그룹에 속한다. 모든 학생은 정확히 한 그룹에 속하고, 모든 그룹의 인원은 같다.

그룹의 실력 수준은 그 그룹에 속한 학생들의 실력 수준의 합이다. 위치와 $k$를 적절히 골라 $x_{\max}/x_{\min}$을 최소로 만들어라. 여기서 $x_{\max}$는 실력 수준이 가장 높은 그룹의 값, $x_{\min}$은 가장 낮은 그룹의 값이다.