Background

Lianzi is studying the motion of molecules.

Each molecule has a velocity. By convention, the positive direction is positive, and the negative direction is negative. There are a huge number of molecules, and their velocities are not the same, so everything looks messy. Therefore, Lianzi wants to adjust the velocities of some molecules so that, in the end, the molecules look neat.

Problem Description

Lianzi is given $n$ integers $a_1,a_2,\cdots a_n$ to describe each molecule. Now she can perform at most $m$ operations (she may also perform none). In each operation, she can do one of the following:

• Choose an index $i$ such that $a_i=\min_j\{a_j\}$, and then change $a_i$ to $\max_j\{a_j\}$.
• Choose an index $i$ such that $a_i=\max_j\{a_j\}$, and then change $a_i$ to $\min_j\{a_j\}$.

Now Lianzi wants to minimize the final range of the sequence (the maximum value minus the minimum value). Please output the minimum possible range.

For example, for the sequence $a=\{5,1,4\}$, you can perform the following operations:

• Choose $i=1$, where $a_1=5$ is the current maximum value $5$, and change $a_1$ to the current minimum value $1$. The sequence becomes $\{1,1,4\}$.
• Then choose $i=2$, where $a_2=1$ is the current minimum value $1$, and change $a_2$ to the current maximum value $4$. The sequence becomes $\{1,4,4\}$.

After these two operations, the sequence is $\{1,4,4\}$. The difference between the maximum and minimum is $|4-1|=3$.

Of course, the range obtained this way is not minimal. The optimal strategy is to first change the maximum $a_1=5$ to the current minimum value $1$, and then change the current maximum $a_3=4$ to the current minimum value $1$. The sequence becomes $\{1,1,1\}$, and the range $|1-1|=0$ is the smallest among all strategies.

Input Format

• The first line contains two positive integers $n,m$, representing the length of the sequence and the maximum number of operations you can perform.
• The second line contains $n$ integers $a$, describing the given sequence.

Output Format

• Output one integer in a single line, representing the minimum range that can be obtained under the optimal strategy.

3 2
5 1 4

0

8 0
1 2 3 4 5 6 7 8

7

8 3
1 5 5 5 6 6 9 10

4

Hint

Sample Explanation

Sample $1$: $\{5,1,4\}\to\{1,1,4\}\to\{1,1,1\}$, the range is $0$.
Sample $2$: $\{1,2,3,4,5,6,7,8\}$, you cannot do anything, the range is $7$.
Sample $3$: $\{1,5,5,5,6,6,9,10\}\to\{10,5,5,5,6,6,9,10\}\to\{5,5,5,5,6,6,9,10\}\to\{5,5,5,5,6,6,9,5\}$, the range is $4$.

Constraints and Notes

For all testdata, it is guaranteed that $1\le n \le 10^5$, $0\le m\le10^9$, $|a_i|\le 10^9$.

Translated by ChatGPT 5