Trạm phát sóng

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ồ, đánh số từ $0$ đến ${10}^6-1$ (điểm ${10}^6-1$ kề với điểm $0$). 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_i$ ($1\le i\le N$).

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. Vị trí trạm phát có thể được đặt cùng vị trí của một trạm thu nào đó.

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

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $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_i$ là vị trí trạm thu sóng thứ $i$ ($0\le a_i<{10}^6$, $1\le i\le N$). Không có hai trạm nào cùng vị trí.
• Dòng cuối cùng chứa số nguyên $K$ là số trạm phát sóng ($1\le K<N$).

Dữ liệu 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.

Ràng buộc

• $1\le K<N\le {10}^3$.
• $0\le a_i<{10}^6$, các $a_i$ đôi một khác nhau.

Ví dụ