Minimizing Range by Extreme Flipping

You are given an array of n integers \(a_1,a_2,\dots,a_n\). You are allowed to perform at most \(m\) operations (possibly zero). In each operation you may choose one of the following two moves:

• Choose an index \(i\) such that \(a_i=\min_{1\le j\le n} \{a_j\}\), and change \(a_i\) to \(\max_{1\le j\le n} \{a_j\}\).
• Choose an index \(i\) such that \(a_i=\max_{1\le j\le n} \{a_j\}\), and change \(a_i\) to \(\min_{1\le j\le n} \{a_j\}\).

The goal is to minimize the range of the final array, i.e. the difference between the maximum and minimum elements. Note that during operations, only an element that is exactly equal to the current minimum or maximum can be changed. In other words, if you flip only part of the occurrences at one extreme, the extreme value remains, so the operation has no effect on the range.

Example:

Consider the array \(a=\{5,1,4\}\). One sequence of operations is as follows:

1. Choose \(i=1\) (since \(a_1=5\) is the maximum), and change it to the current minimum \(1\). The array becomes \(\{1,1,4\}\).
2. Then choose \(i=2\) (since \(a_2=1\) is the minimum), and change it to the current maximum \(4\). The array becomes \(\{1,4,4\}\).

The range is \(|4-1|=3\). However, an optimal strategy is to perform the following:

1. Choose \(i=1\) with \(a_1=5\) (maximum) and change it to \(1\). The array becomes \(\{1,1,4\}\).
2. Then choose \(i=3\) with \(a_3=4\) (now the maximum) and change it to \(1\). The array becomes \(\{1,1,1\}\).

The final range is \(0\), which is the minimum possible.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of elements and the maximum allowed operations). The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\), representing the array.

outputFormat

Output a single integer: the minimum possible range of the array (i.e. \(\max\{a\} - \min\{a\}\)) achievable after at most \(m\) operations.

sample

3 2
5 1 4

0