Trong chương trình chuyển đổi số quốc gia, nhóm sinh viên tình nguyện của Khoa Công nghệ Thông tin - Trường ĐH CNTT và Truyền thông (ICTU) thực hiện dự án lắp đặt trạm phát sóng WiFi miễn phí cho N hộ gia đình dọc theo tuyến đường quốc lộ tại các xã vùng xa.

Các hộ gia đình nằm rải rác trên một trục đường thẳng (coi là trục tọa độ OX), nhà thứ i có tọa độ là \(X_i\). Nhóm chỉ được cấp kinh phí để lắp đặt tối đa K trạm phát sóng. Mỗi trạm phát sóng khi được đặt tại vị trí P bất kỳ sẽ có bán kính phủ sóng là R. Điều này có nghĩa là tất cả các ngôi nhà nằm trong đoạn [P - R, P + R] đều sẽ có tín hiệu mạng. Để tiết kiệm chi phí vận hành mà vẫn đảm bảo 100% hộ dân đều có sóng WiFi, nhóm nghiên cứu cần tìm ra giá trị bán kính R nhỏ nhất có thể.

Nhiệm vụ:

Hãy giúp nhóm nghiên cứu ICTU xác định bán kính R tối ưu này.

Dữ liệu vào (Input):

• Dòng 1: Hai số nguyên N và K \((1 ≤ K ≤ N ≤ 10^5)\) là số hộ gia đình và số trạm phát sóng
• Dòng 2: N số nguyên \(X_1, X_2, ..., X_n\) đã được sắp xếp tăng dần với Xi là tọa độ của nhà thứ i \((0 ≤ X_i ≤ 10^9)\)

Kết quả ra (Output):

• Một số thực là giá trị R nhỏ nhất tìm được là bán kính tối ưu, làm tròn đúng 1 chữ số thập phân.

Input :

3 1
1 3 5

Output :

2.0

Giải thích

Có 3 nhà tại tọa độ 1, 3, 5. Chỉ có 1 trạm. Ta đặt trạm đặt tại tọa độ 3.0 sẽ phủ được toàn bộ khoảng cách từ 1.0 đến 5.0 (bán kính R=2.0).

Ràng buộc:

• Có 30% số điểm tương ứng với N, K ≤ 10
• Có 40% số điểm tương tứng với N, K ≤ 2000
• Có 30% số điểm còn lại không có ràng buộc gì thêm (full test) \((1 ≤ K ≤ N ≤ 10^5; 0 ≤ X_i ≤ 10^9)\)
• Thời gian: ≤ 1.0s
• Bộ nhớ: ≤ 256MB.