Along a straight service road there are n candidate mounting posts at distinct integer positions. You must switch on exactly k of them as signal towers. To reduce interference you want the two closest active towers to be as far apart as possible.
Choose k of the positions so that the minimum distance between any two chosen positions is maximized, and print that maximized minimum distance.
Input format
Line 1: an integer n, the number of candidate positions.
Line 2: n space-separated distinct integers, the positions (in any order).
Line 3: an integer k, the number of towers to switch on.
Output format
A single integer: the largest achievable minimum distance between chosen towers.
Constraints
- 2 <= k <= n <= 100000
- 0 <= each position <= 1000000000
- All positions are distinct.