A lab records n numeric readings. Consider every unordered pair of distinct positions (i, j) and its gap |a[i] - a[j]|. If all n * (n - 1) / 2 gaps are listed in non-decreasing order, print the k-th one (1-indexed).
Gaps of value 0 are allowed (they occur when two readings are equal) and count normally.
Input format
Line 1: an integer n, the number of readings.
Line 2: n space-separated integers, the readings.
Line 3: an integer k with 1 <= k <= n * (n - 1) / 2.
Output format
A single integer: the k-th smallest pairwise absolute difference.
Constraints
- 2 <= n <= 100000
- -1000000000 <= each reading <= 1000000000
- 1 <= k <= n * (n - 1) / 2