Trạm BTS

Dọc theo một con đường Quốc lộ có $n$ địa điểm dân cư. Để đơn giản ta có thể coi các địa điểm này như là các điểm trên trục toạ độ $Ox$ với các hoành độ lần lượt là $x_1,x_2,\dots ,x_n$.

Công ty viễn thông ABC có kế hoạch lắp $k$ trạm BTS tại các vị trí trên đường (mỗi vị trí có thể xem như là một điểm trên trục toạ độ) với "bán kính phủ sóng" đều bằng số nguyên dương $R$. Nếu một trạm BTS được đặt tại vị trí có hoành độ $x$ thì nó có thể phủ sóng cho tất cả các điểm dân cư có vị trí nằm trong đoạn $[x-R,x+R]$.

Yêu cầu: Tìm giá trị $R$ nhỏ nhất để có thể bố trí cách lắp đặt $k$ trạm BTS sao cho mỗi điểm dân cư đều nằm trong vùng phủ sóng của ít nhất một trạm.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương $n,k$.
• Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\dots ,x_n$.

Dữ liệu ra

Một số nguyên dương duy nhất là giá trị nhỏ nhất của $R$ tìm được.

Ràng buộc

• $1\le k\le n\le {10}^5$.
• $|x_i|\le {10}^9$, các $x_i$ đôi một khác nhau ($x_i\ne x_j$ với $i\ne j$).

Subtasks

• Subtask 1 ($25\%$ số điểm): $k=1$.
• Subtask 2 ($25\%$ số điểm): $k=2$.
• Subtask 3 ($25\%$ số điểm): $n\le 300$.
• Subtask 4 ($25\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ