알파카 목장에는 일직선 도로를 따라 N개의 축사가 있다. \(i\)번째 축사는 좌표 \(x_i\)에 위치한다.

목장 주인은 사나운 알파카 C마리를 이 축사들 중 서로 다른 C곳에 한 마리씩 배치하려고 한다. 알파카끼리 너무 가까이 있으면 서로 싸우기 때문에, 배치된 알파카들 중 가장 가까운 두 마리 사이의 거리가 최대가 되도록 배치하고 싶다.

알파카를 가장 적절하게 배치했을 때, 가장 가까운 두 알파카 사이 거리의 최댓값을 구하여라. 두 축사 \(x_i, x_j\) 사이의 거리는 \(|x_i - x_j|\) 이다.

• \(2 ≤ C ≤ N ≤ 200\,000\)
• \(0 ≤ x_i ≤ 1\,000\,000\,000\)
• 모든 \(x_i\)는 서로 다르다.

첫째 줄에 축사의 개수 \(N\)과 배치할 알파카의 수 \(C\)가 공백으로 구분되어 주어진다.

둘째 줄에 \(N\)개의 축사 좌표 \(x_1, x_2, \dots, x_N\)이 공백으로 구분되어 주어진다. 모든 좌표는 서로 다르다.

가장 가까운 두 알파카 사이 거리의 최댓값을 한 줄에 출력한다.

rip 작성

출처 Original