Все мы слышали захватывающие истории о приключениях Робина Гуда, который, будучи великолепным лучником, воровал деньги у богатых и раздавал их бедным.
В Кекландии проживает n человек, при этом у человека номер i изначально имеется ci монет. Каждый день Робин Гуд отбирает 1 монету у самого богатого человека и отдаёт её самому бедному человеку (самому бедному, после того как он уже забрал 1 монету у самого богатого). Если самого богатого или самого бедного невозможно выбрать однозначно, то из подходящих вариантов Робин Гуд выбирает одного случайного. К сожалению, Робин Гуд уже стар и через k дней уйдёт на пенсию. Он решил провести все эти дни отбирая деньги у богатых и раздавая бендым.
После того как Робин Гуд отбирает монету у самого богатого, этот человек может стать самым бедным, и может даже так произойти, что Робин Гуд отдаст ему его монету назад. Например, если в какой-то день у всех жителей одинаковое количество монет, то и на следующий день у всех жителей также будет одинаковое количество монет.
Вам поручено найти разность количества денег у самого богатого и самого бедного человека через k дней. Обратите внимание, что случайность выбора среди самых богатых и самых бедных не влияет на ответ.
Примечание
Проследим как изменяется богатство людей в первом примере.
- [1, 1, 4, 2]
- [2, 1, 3, 2] или [1, 2, 3, 2]
Таким образом, ответ равен 3 - 1 = 2.
Во втором примере никаких изменений происходить не будет.