Minimizing Difference

Description:

Input:

The first line contains two integers $$$n$$$ and $$$k$$$ $$$(2 \le n \le 10^{5}, 1 \le k \le 10^{14})$$$ — the number of elements in the sequence and the maximum number of times you can perform the operation, respectively.

The second line contains a sequence of integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^{9})$$$.

Output:

Print the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than $$$k$$$ times.

Sample Input:

4 5
3 1 7 5

Sample Output:

2

Sample Input:

3 10
100 100 100

Sample Output:

0

Sample Input:

10 9
4 5 5 7 5 4 5 2 4 3

Sample Output:

1

Note:

In the first example you can increase the first element twice and decrease the third element twice, so the sequence becomes $$$[3, 3, 5, 5]$$$, and the difference between maximum and minimum is $$$2$$$. You still can perform one operation after that, but it's useless since you can't make the answer less than $$$2$$$.

In the second example all elements are already equal, so you may get $$$0$$$ as the answer even without applying any operations.