Các trạm thu, phát sóng viễn thông của thành phố được đặt trên một đường tròn. Đường tròn này được chia thành ~10^6~ điểm cách đều nhau theo chiều kim đồng hồ. Một vị trí trên đường tròn được chọn là mốc 0. Có N trạm thu sóng được đánh thứ tự từ 1 đến N, trạm thứ i đặt ở vị trí aᵢ.

Thành phố dự kiến sẽ đầu tư K trạm phát sóng với phạm vi phát như nhau. Tuy nhiên, một trạm phát sóng với phạm vi phát càng dài thì chi phí càng cao. Vì vậy, thành phố cần tính toán để đầu tư các trạm phát sóng có phạm vi phát ngắn nhất và phải đảm bảo các trạm thu sóng đều nhận được tín hiệu.

Khi một trạm phát sóng có phạm vi phát là R thì các trạm thu sóng trong khoảng cách R theo cả hai chiều kim đồng hồ đều nhận được tín hiệu. Ví dụ: Trạm phát sóng tại vị trí 3 với phạm vi phát 1 thì cả trạm thu sóng ở vị trí 2 và 4 đều nhận được tín hiệu.

Yêu cầu

Tìm phạm vi phát ngắn nhất của K trạm phát sóng để N trạm thu sóng đều nhận được tín hiệu.

Dữ liệu vào: TPS.INP

• Dòng đầu tiên chứa số nguyên dương N, thỏa mãn: ~1 \le N \le 10^3~
• Dòng thứ i trong N dòng tiếp theo chứa một số nguyên aᵢ là vị trí trạm thu sóng thứ i. Không có hai trạm nào cùng vị trí, thỏa mãn: ~0 \le a_i < 10^6~, ~1 \le i \le N~
• Dòng cuối cùng chứa số nguyên K là số trạm phát sóng, thỏa mãn: ~1 \le K < N~ Chú ý: vị trí trạm phát có thể được đặt cùng vị trí của một trạm thu nào đó.

Kết quả: TPS.OUT

Ghi ra một số nguyên duy nhất là phạm vi phát sóng ngắn nhất của K trạm phát.

Ví dụ

Sample Input

4
5
1000
12345
987
2

Sample Output

498

Giải thích: Đặt một trạm phát sóng ở vị trí 503 và một trạm phát sóng ở vị trí 12340 có phạm vi phát sóng là 498.

Sample Input

2
1
999999
1

Sample Output

1

Giải thích: Đặt một trạm phát sóng ở vị trí 0 có phạm vi phát sóng là 1.