import java.util.*;

class DH_43236 {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        int s = 0, e = distance;

        Arrays.sort(rocks);

        // 각 지점 사이의 최소 거리를 조절하면서 정답 구하기
        while(s <= e) {
            int m = (s + e) / 2;

            // 최소 길이가 middle가 될 수 있을 때
            // 제거해야되는 최소 돌의 개수
            int tmp = removeCnt(rocks, m, distance);

            // 제거해야되는 돌의 개수가 주어진 값보다 같거나 작으면
            // 현재 값이 작아서 다른 큰 값들이 많다는 의미
            // 현재 값의 크기를 키워줘야 됨
            if(tmp <= n) {
                answer = m;
                s = m + 1;
            // 제거해야 되는 돌의 개수가 주어진 값보다 크다면
            // 해당 값보다 작은 값들이 많아서 작은 거리을 없애기 위해 돌을 많이 없애야 된다는 의미
            // 현재 값을 줄여줘야 됨
            } else {
                e = m - 1;
            }
        }
        return answer;
    }

    // 제거해야되는 바위 개수 세는 함수
    static int removeCnt(int[] rocks, int m, int distance) {

        // mid가 바위 간 최소 거리가 되어야 함
        int removeCnt = 0;
        int before = 0;

        for(int i = 0; i < rocks.length + 1; i++) {
            int current = i == rocks.length ? distance: rocks[i];

            // 두 지점 사이 간격이 m보다 작다면 해당 바위 제거해야 됨
            if(current - before < m) {
                removeCnt++;
                continue;
            }

            if(i == rocks.length) break;
            before = rocks[i];
        }

        return removeCnt;
    }
}