Các trạm thu, phát sóng viễn thông của thành phố được đặt tên 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. 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.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(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 phát sóng thứ \(i\). Không có hai trạm nào cùng vị trí \((0 \le a_i \le 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 \lt 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 đó.

Dữ liệu ra

• 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

Input 1

4
5
1000
12345
987
2

Ouput 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

Input 2

2
1
999999
1

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