Cuội và Bờm đến thăm thành phố Mơ Ước. 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_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. 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.

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.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 10^3)~.
• ~N~ dòng tiếp theo, mỗi dòng 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)~.
• Dòng cuối cùng chứa số nguyên ~K~ ~(1 \le K < N)~.

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

Sample Input 2

2
1
999999
1

Sample Output 2

1