K-ésima Menor Diferença
Dado um array de $N$ inteiros, todo par de índices distintos $(i, j)$ com $i < j$ define uma diferença absoluta $|A_i - A_j|$. No total existem
$$\binom{N}{2} = \frac{N \cdot (N-1)}{2}$$
pares possíveis. Essa é a notação de combinação: quantas formas existem de escolher 2 elementos de um conjunto de $N$. Por exemplo, com $N = 5$ há $\frac{5 \cdot 4}{2} = 10$ pares.
Se listarmos todas essas diferenças em ordem não-decrescente, sua tarefa é encontrar a $K$-ésima da lista (indexação a partir de $1$).
Input
A primeira linha contém dois inteiros $N$ e $K$ $\left(2 \le N \le 10^6,\ 1 \le K \le \dfrac{N(N-1)}{2}\right)$.
A segunda linha contém $N$ inteiros $A_i$ $(0 \le A_i \le 10^9)$.
Output
Imprima um único inteiro: a $K$-ésima menor diferença absoluta.
5 4 1 6 3 8 2
2
Explanation 1:
Com $N = 5$ há $\binom{5}{2} = 10$ pares. Listando todos com suas diferenças:
| Par $(i, j)$ | $A_i$ | $A_j$ | $\|A_i - A_j\|$ |
|:---:|:---:|:---:|:---:|
| (0,1) | 1 | 6 | 5 |
| (0,2) | 1 | 3 | 2 |
| (0,3) | 1 | 8 | 7 |
| (0,4) | 1 | 2 | 1 |
| (1,2) | 6 | 3 | 3 |
| (1,3) | 6 | 8 | 2 |
| (1,4) | 6 | 2 | 4 |
| (2,3) | 3 | 8 | 5 |
| (2,4) | 3 | 2 | 1 |
| (3,4) | 8 | 2 | 6 |
Ordenando as 10 diferenças:
$$\underbrace{1}_{1^\circ},\ \underbrace{1}_{2^\circ},\ \underbrace{2}_{3^\circ},\ \underbrace{2}_{4^\circ},\ 3,\ 4,\ 5,\ 5,\ 6,\ 7$$
A $4^\text{a}$ menor é $\mathbf{2}$.
4 6 0 10 20 30
30
Explanation 2:
Com $N = 4$ há $\binom{4}{2} = 6$ pares:
| Par | Diferença |
|:---:|:---:|
| (0,10) | 10 |
| (0,20) | 20 |
| (0,30) | 30 |
| (10,20) | 10 |
| (10,30) | 20 |
| (20,30) | 10 |
Ordenadas: $10,\ 10,\ 10,\ 20,\ 20,\ 30$. A $6^\text{a}$ (última) é $\mathbf{30}$.
2 1 0 0
0
6 15 0 1 2 3 4 5
5