컴퓨터 과학

시간 제한2초메모리 제한512 MB

요약

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

난이도: 어려움10점 중 8점
유형: 이분 탐색, 정렬, 투 포인터, 누적 합
정답자: 아직 제출이 없습니다

문제

베라에게 정수 $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$ 으로 고르면 된다. 아래 그림이 그 선택을 나타낸다.

예제4

예제 1
입력
```
5 3
1 -2 10 5 4
```
예상 출력
```
6
```
예제 2
입력
```
1 1
0
```
예상 출력
```
0
```
예제 3
입력
```
5 1
-1000000000 1000000000 0 7 -7
```
예상 출력
```
0
```
예제 4
입력
```
4 4
1 5 2 9
```
예상 출력
```
8
```