说明

数对 ($a,b$) 由整数$a$和$b$组成，其数对距离定义为$a$和$b$的绝对差值。

给你一个整数数组 nums 和一个整数$k$ ，数对由$nums[i]$和$nums[j]$ 组成且满足$0 \leqslant i < j < nums.length$。返回 所有数对距离中 第 $k$ 小的数对距离。

输入格式

第一行一个整数$n$,表示整数数组 nums元素的个数

第二行整数数组 nums,$n$个元素，空格隔开

第三行一个整数$k$

输出格式

输出所有数对距离中 第 $k$ 小的数对距离

样例

3
1 3 1
1

0

样例1解释：数对和对应的距离如下：

(1,3) -> 2

(1,1) -> 0

(3,1) -> 2

距离第 1 小的数对是 (1,1) ，距离为 0 。

3
1 1 1
2

0

3
1 6 1
3

5

数据范围

$n == nums.length$

$2 \leqslant n \leqslant 10^4$

$0 \leqslant nums[i] \leqslant 10^6$

$1 \leqslant k \leqslant n * (n - 1) / 2$

来源

LeetCode 719