수영 대회

시간 제한1초메모리 제한1024 MB

요약

정렬한 수영 기록을 크기가 A 이상 B 이하인 연속 구간으로 나누어, 각 구간의 최대-최소 차이 중 최댓값을 최소로 만든다.

문제

비트랜디아(Bitlandia)에서는 모든 학생이 오픈 수영 대회에 참가할 수 있다. 사전 등록이 필수가 아니므로, 주최 측은 몇 명이 참가할지 미리 알 수 없다.

올해 참가하는 학생 수는 비트랜디아의 수영 레인 수인 500 000보다 적다. 주최 측은 참가자를 각 그룹에 최소 $A$ 명, 최대 $B$ 명이 되도록 여러 그룹으로 나누기로 했다.

또한 주최 측은 각 그룹에 속한 수영 선수들의 속도를 최대한 비슷하게 맞추어 대회를 더 재미있게 만들고자 한다.

수영 선수들을 그룹으로 나눌 때, 모든 그룹에 대해 '그 그룹에서 가장 느린 선수와 가장 빠른 선수의 기록 차이'의 최댓값이 가능한 한 작아지도록 나누는 프로그램을 작성하시오.

첫째 줄에 세 정수, 즉 대회에 참가한 인원 수 $N$ 과 각 그룹에 들어갈 수 있는 최소 인원 $A$ , 최대 인원 $B$ 가 주어진다.

이어지는 $N$ 개의 줄에는 각 선수가 거리를 완주하는 데 걸리는 시간 $t_i$ 가 한 줄에 하나씩 주어진다.

입력은 항상 유효한 분할이 존재하도록 주어진다.

모든 그룹에 대해 가장 느린 선수와 가장 빠른 선수의 기록 차이를 구했을 때, 그 최댓값이 될 수 있는 가장 작은 값을 하나의 정수로 출력한다.