Решение задачи Выборы с Codeforces

Аурук принимает участие в выборах в своей школе. Это последний раунд. У него есть ровно один оппонент — Элодрейп. В школе есть ровно n студентов. У каждого студента есть ровно k голосов и он обязан использовать их все. Тем самым, Аурук понимает, что если какой-то человек отдаёт ai голосов за Элодрейпа, то ему достанется k−ai голосов от этого человека. Конечно, должно выполняться 0≤k−ai.

Аурук знает, что если он проиграет, то его жизнь всё равно что кончится. Он поговорил со своими друзьями и теперь знает a1,a2,…,an — сколько голосов каждый школьник отдаст за Элодрейпа. Теперь он хочет поменять число k, чтобы выиграть выборы. Он понимает, что чем больше k, тем больше шансов, что кто-то заметит неладное, и что его дисквалифицируют.

Тем самым, Аурук знает a1,a2,…,an — сколько голосов каждый из школьников отдаст его оппоненту. Помогите ему выбрать наименьшее k, которое приведёт к его выигрышу. Чтобы выиграть, Аурук должен набрать строго больше голосов, чем Элодрейп.