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~). 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.

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.

Input

• 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~. Không có hai trạm nào cùng vị trí (~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 (~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 đó.

Output

• 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.

Sample Input 1

4 
5 
1000 
12345 
987 
2

Sample Output 1

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

2 
1 
999999 
1

Sample Output 2

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.