Computer Science

Time limit2sMemory limit512 MB

Summary

Find the smallest L such that for each a_i we can pick an interval [x_i, x_i+L] covering a_i and containing at least K of the given integers.

Level: Hard8 of 10
Topics: Binary search, Sorting, Two pointers, Prefix sum
Solved: No attempts yet

Problem

Vera has $N$ integers $a_1, \ldots, a_N$ .

A margin is a non-negative integer $L$ with the following property. You can choose $N$ integers $x_1, \ldots, x_N$ so that for every $i$ with $1 \le i \le N$ , the interval $[x_i, x_i + L]$ contains at least $K$ of Vera's integers and also contains $a_i$ . Equal values are counted separately, so a value that appears three times counts three times.

Compute the minimum possible margin.

Input

The first line contains integers $N$ and $K$ ( $1 \le K \le N \le 2 \times 10^5$ ).

The second line contains $N$ integers $a_1, \ldots, a_N$ ( $-10^9 \le a_i \le 10^9$ ).

Output

Print one line with one integer, the minimum possible margin.

Hint

For the first example, one valid choice is $x_1 = -1$ , $x_2 = -2$ , $x_3 = 4$ , $x_4 = 0$ , $x_5 = 0$ . The picture below shows that choice.

Examples4

Example 1
Input
```
5 3
1 -2 10 5 4
```
Expected output
```
6
```
Example 2
Input
```
1 1
0
```
Expected output
```
0
```
Example 3
Input
```
5 1
-1000000000 1000000000 0 7 -7
```
Expected output
```
0
```
Example 4
Input
```
4 4
1 5 2 9
```
Expected output
```
8
```