Mấy ông nông dân này!
Kì thi Olympic Tin Học \(2023\) ở Huế, Tú Anh được gặp thầy Nhã và đội UTC2. Thầy Nhã hay trêu các anh bằng câu: "Mấy cái ông nông dân này" :))). Tú Anh liền nghĩ ra câu đố thầy như sau:
Một nông dân có trang trại và \(N\) cái cọc, các cọc được đặt trên một đường thẳng ở các vị trí \(x_1, x_2, ..., x_n\). Trang trại có \(C\) con bò. Tất các các con bò đều không ưa nhau. Để tránh mấy con bò trở nên nóng tính và làm tổn thương nhau, nông dân phải đặt mỗi con bò vào cọc sao cho khoảng cách nhỏ nhất giữa hai con bò bất kì là lớn nhất. Tìm giá trị lớn nhất này.
Vì thầy Nhã rất bận, không có thời gian trả lời câu hỏi vô tri này của Tú Anh, nên các bạn hãy giúp thầy nhé :>
Input
Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(C\) \((2 \le C \le N \le 10^5)\).
\(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(x_i\) mô tả vị trí của một cây cọc \((0 \le x_i \le 10^9)\).
Output
In ra giá trị lớn nhất của khoảng cách nhỏ nhất giữa hai con bò bất kì.
Example
Sample Input
5 3
1
2
8
4
9Sample Output
3
Comments
Nản? Mình dùng hàng đợi ưu tiên mà chỉ pass có 02 test