컴퓨터 과학

각 a_i를 포함하면서 주어진 정수를 K개 이상 담는 구간 [x_i, x_i+L]을 고를 수 있게 하는 최소 L을 구한다.

어려움8이분 탐색정렬투 포인터누적 합아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제4

문제

베라에게 정수 $N$ 개 $a_1, \ldots, a_N$ 이 있다.

여유값은 다음 조건을 만족하는 음이 아닌 정수 $L$ 이다. 정수 $x_1, \ldots, x_N$ 을 적절히 골라서, $1 \le i \le N$ 인 모든 $i$ 에 대해 구간 $[x_i, x_i + L]$ 이 베라의 정수 중 $K$ 개 이상을 포함하고 $a_i$ 도 포함하게 만들 수 있으면 $L$ 은 여유값이다. 값이 같은 정수가 여러 개 있으면 각각 따로 센다.

여유값의 최솟값을 구하라.

입력

첫째 줄에 정수 $N$ 과 $K$ 가 주어진다. ( $1 \le K \le N \le 2 \times 10^5$ )

둘째 줄에 정수 $N$ 개 $a_1, \ldots, a_N$ 이 주어진다. ( $-10^9 \le a_i \le 10^9$ )

출력

여유값의 최솟값을 정수 하나로 한 줄에 출력한다.

힌트

첫 번째 예제에서는 $x_1 = -1$ , $x_2 = -2$ , $x_3 = 4$ , $x_4 = 0$ , $x_5 = 0$ 으로 고르면 된다. 아래 그림이 그 선택을 나타낸다.