В данной задаче вам задана последовательность \(a_1, a_2, \dots, a_n\), состоящая из \(n\) целых чисел.
Вы можете изменять элементы последовательности. В ходе одной операции изменения, вы можете выбрать произвольную позицию в последовательности и увеличить или уменьшить элемент, находящийся в этой позиции, на единицу.
Перед вами стоит задача определить минимально возможную разность между максимальным и минимальным элементами последовательности, которую можно достичь, произведя не более \(k\) описанных операций.
Выходные данные
Выведите минимально возможную разность между максимальным и минимальным элементами последовательности, которую можно достичь, произведя не более \(k\) операций, описанных в условии.
Примечание
В первом примере можно дважды увеличить на единицу второе число и дважды уменьшить на единицу третье число. Тогда получим последовательности \([3, 3, 5, 5]\), в которой разность между максимальным и минимальным элементами равна \(2\). При этом останется одна еще операция, но ее можно не использовать, так как не удастся сделать разность между максимальным и минимальным элементами меньше \(2\).
Во втором примере можно не использовать ни одной операции, так как все элементы в последовательности одинаковые, а значит разность между максимальным и минимальным элементами равна \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
3 1 7 5
|
2
|
|
2
|
3 10
100 100 100
|
0
|
|
3
|
10 9
4 5 5 7 5 4 5 2 4 3
|
1
|