E. Минимизация разности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В данной задаче вам задана последовательность $$$a_1, a_2, \dots, a_n$$$, состоящая из $$$n$$$ целых чисел.

Вы можете изменять элементы последовательности. В ходе одной операции изменения, вы можете выбрать произвольную позицию в последовательности и увеличить или уменьшить элемент, находящийся в этой позиции, на единицу.

Перед вами стоит задача определить минимально возможную разность между максимальным и минимальным элементами последовательности, которую можно достичь, произведя не более $$$k$$$ описанных операций.

Входные данные

В первой строке следуют два целых числа $$$n$$$ и $$$k$$$ $$$(2 \le n \le 10^{5}, 1 \le k \le 10^{14})$$$ — количество элементов в последовательности и максимальное количество операций изменения элементов, которое можно произвести.

Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^{9})$$$.

Выходные данные

Выведите минимально возможную разность между максимальным и минимальным элементами последовательности, которую можно достичь, произведя не более $$$k$$$ операций, описанных в условии.

Примеры
Входные данные
4 5
3 1 7 5
Выходные данные
2
Входные данные
3 10
100 100 100
Выходные данные
0
Входные данные
10 9
4 5 5 7 5 4 5 2 4 3
Выходные данные
1
Примечание

В первом примере можно дважды увеличить на единицу второе число и дважды уменьшить на единицу третье число. Тогда получим последовательности $$$[3, 3, 5, 5]$$$, в которой разность между максимальным и минимальным элементами равна $$$2$$$. При этом останется одна еще операция, но ее можно не использовать, так как не удастся сделать разность между максимальным и минимальным элементами меньше $$$2$$$.

Во втором примере можно не использовать ни одной операции, так как все элементы в последовательности одинаковые, а значит разность между максимальным и минимальным элементами равна $$$0$$$.