Background

Lotus is studying the movement of molecules.

Each molecule has a speed, with the positive direction being positive and the negative direction being negative. The number of molecules is extremely large, and their speeds are not consistent, appearing chaotic. Therefore, Lotus hopes to adjust the speeds of some molecules so that the molecules look orderly.

Problem Description

Lotus has given \( n \) integers \( a_1, a_2, \cdots, a_n \), describing each molecule. Now, she can perform at most \( m \) operations (or none at all). Each operation can execute one of the following two actions:

• Choose \( i \) such that \( a_i = \min_j\{a_j\} \), and then change \( a_i \) to \( \max_j\{a_j\} \).
• Choose \( i \) such that \( a_i = \max_j\{a_j\} \), and then change \( a_i \) to \( \min_j\{a_j\} \).

Lotus hopes to minimize the range (the difference between the maximum and minimum values) of the final sequence. Please find the minimum range.

For example, for the sequence \( a = \{5, 1, 4\} \), the following operations can be performed:

• Choose \( i = 1 \), where \( a_1 = 5 \) is the current maximum value, and change \( a_1 \) to the current minimum value \( 1 \), resulting in the sequence \( \{1, 1, 4\} \);
• Then choose \( i = 2 \), where \( a_2 = 1 \) is the current minimum value, and change \( a_2 \) to the current maximum value \( 4 \), resulting in the sequence \( \{1, 4, 4\} \).

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

However, this method does not yield the smallest range. The optimal strategy is to first change the maximum value \( a_1 = 5 \) to the current minimum value \( 1 \), and then change the current maximum value \( a_3 = 4 \) to the current minimum value \( 1 \). The sequence then 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 \) and \( m \), representing the length of the sequence and the maximum number of operations you can perform, respectively.
• The second line contains \( n \) integers \( a \), describing the given sequence.

Output Format

• Output a single integer on one line, representing the minimum range that can be achieved with the optimal strategy.

Sample Input and Output

Sample Input #1

3 2
5 1 4

Sample Output #1

0

Sample Input #2

8 0
1 2 3 4 5 6 7 8

Sample Output #2

7

Sample Input #3

8 3
1 5 5 5 6 6 9 10

Sample Output #3

4

Notes

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\} \), no operations can be performed, 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 \).

Data Range and Constraints

For all data, it is guaranteed that \( 1 \le n \le 10^5 \), \( 0 \le m \le 10^9 \), and \( |a_i| \le 10^9 \).

见题面 Input 部分

见题面 Output 部分