수영 대회

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

요약

정렬된 N명의 기록을 A명 이상 B명 이하의 연속한 조로 나눌 때, 각 조에서 가장 빠른 기록과 가장 느린 기록의 차이 중 최댓값을 최소로 만드는 값을 구한다.

문제

학생 공개 수영 대회에는 원하는 학생이면 누구나 참가할 수 있다. 사전 등록이 필요 없기 때문에 주최 측은 몇 명이 참가할지 미리 알 수 없다.

수영장에는 레인이 8개 있지만, 이번에는 예상보다 적은 학생이 왔다. 그래서 주최 측은 참가자들을 한 조에 최소 $A$ 명, 최대 $B$ 명씩 들어가는 작은 조들로 나누기로 했다.

또한 주최 측은 각 경기가 최대한 흥미진진하도록, 실력이 비슷한 선수들이 한 조에서 겨루기를 원한다.

도착한 학생들을 여러 조로 나누되, 어떤 조에서든 그 조에 속한 가장 느린 선수와 가장 빠른 선수의 평균 완주 시간 차이(절댓값) 중 가장 큰 값이 최소가 되도록 하는 프로그램을 작성하라.

첫 번째 줄에는 공백으로 구분된 세 정수가 주어진다: 참가한 선수 수 $N$ , 그리고 한 조에 들어갈 수 있는 최소 인원 $A$ 와 최대 인원 $B$ .

이어지는 $N$ 개의 줄에는 각 선수가 거리를 완주하는 평균 시간 $t_i$ 가 오름차순으로 주어진다 ( $t_i \le t_{i+1}$ ).

입력은 항상 조로 나누는 유효한 방법이 존재하도록 주어진다.

모든 참가자를 조로 나누는 유효한 방법에 대해, 한 조 안에서 가장 느린 선수와 가장 빠른 선수의 시간 차이 중 가장 큰 값을 생각한다. 이 값이 가질 수 있는 최소값을 정수 하나로 출력하라.