일직선 도로 위의 서로 다른 \(N\)개의 위치 \(x_1, x_2, \dots, x_N\) 중에서 \(K\)곳을 골라 통신 기지국을 세우려고 한다. 기지국끼리 전파가 간섭하지 않도록, 선택한 기지국들 중 가장 가까운 두 기지국 사이의 거리가 되도록 커지게 만들고 싶다.

\(K\)곳의 위치를 적절히 골랐을 때 얻을 수 있는, 가장 가까운 두 기지국 사이 거리의 최댓값을 구하여라.

\(2 \le K \le N \le 200{,}000\)

\(1 \le x_i \le 10^9\)

모든 \(x_i\)는 서로 다르다.

첫째 줄에 위치의 수 \(N\)과 세울 기지국의 수 \(K\)가 주어진다.

다음 \(N\)개의 줄에 각각 위치의 좌표 \(x_i\) (\(1 \le x_i \le 10^9\))가 주어진다. 모든 좌표는 서로 다르다.

가장 가까운 두 기지국 사이 거리의 최댓값을 출력한다.

riseoj 작성

출처 Original