제자리 멀리뛰기

체육 시간에 제자리 멀리뛰기 훈련을 한다. 훈련장은 끓는 용암으로 가득 차 있어서, 학생은 용암 위에 놓인 돌섬을 딛으며 반대편 탈출구까지 건너가야 한다.

학생이 출발하는 돌섬은 위치 $0$에 있고, 탈출구는 위치 $d$에 있다. 출발 돌섬과 탈출구 사이에는 작은 돌섬이 $n$개 있으며, 각 돌섬의 위치는 출발 돌섬으로부터의 거리로 주어진다.

선생님은 이 $n$개의 작은 돌섬 중 정확히 $m$개를 제거한다. 학생은 남은 $n-m$개의 작은 돌섬을 모두 딛으면서 출발 돌섬에서 탈출구까지 위치 순서대로 점프한다. (두 돌섬이 아무리 멀리 떨어져 있어도 점프는 반드시 성공하며, 용암에 빠지는 일은 없다.)

한 번의 점프 거리는 연속해서 딛는 두 지점 사이의 거리이다. 즉 출발 돌섬, 남은 작은 돌섬들, 탈출구를 위치 순서대로 늘어놓았을 때 이웃한 두 지점 사이의 거리들이 각 점프 거리가 된다.

제거할 $m$개의 돌섬을 잘 골라 학생이 뛰는 점프 거리의 최솟값을 최대로 만들고자 한다. 이때 가능한 최댓값을 구하여라.

첫째 줄에 출발 돌섬에서 탈출구까지의 거리 $d$ ($1 \le d \le 10^9$), 작은 돌섬의 수 $n$ ($0 \le n \le 50000$), 제거할 돌섬의 수 $m$ ($0 \le m \le n$)이 공백으로 구분되어 주어진다.

둘째 줄부터 $n$개의 줄에 걸쳐 각 작은 돌섬의 위치(출발 돌섬으로부터의 거리)가 한 줄에 하나씩 정수로 주어진다. 모든 돌섬의 위치는 서로 다르다.

$m$개의 돌섬을 제거한 뒤 얻을 수 있는, 점프 거리의 최솟값의 최댓값을 한 줄에 출력한다.