Лимак — это мишка гризли, жаждущий власти и признания. Он хочет победить в предстоящих выборах и править всей Берляндией.
Дано n кандидатов, включая Лимака. Мы знаем, сколько граждан собираются проголосовать за каждого кандидата, за i-го кандидата будет отдано ai голосов. Лимак — кандидат номер 1. Чтобы победить на выборах, он должен набрать строго больше голосов, чем любой другой кандидат.
Победа важнее всего, так что Лимак решил сжульничать. Он подкупит некоторых граждан и украдет голоса у своих оппонентов. Чтобы подкупить гражданина, Лимак должен дать ему одну конфетку: граждане — мишки, а мишкам нравятся конфетки. У Лимака немного конфеток и ему интересно, сколько граждан ему надо подкупить?
Выходные данные
Выведите минимальное количество граждан, которых Лимак должен подкупить, чтобы набрать строго больше голосов, чем любой другой кандидат.
Примечание
В первом тесте у Лимака 5 голосов. Один из способов достичь победы — подкупить 4 граждан, желающих проголосовать за третьего кандидата. Количество голосов будет 9, 1, 7, 2, 8 (У Лимака будет 9 голосов). Другой способ — отнять 3 голоса у третьего кандидата и 1 голос у второго кандидата, чтобы получилась следующая ситуация: 9, 0, 8, 2, 8.
Во втором примере Лимак украдет 2 голоса у каждого кандидата. Получится: 7, 6, 6, 6.
В третьем примере Лимак одержит победу, не подкупив ни одного гражданина.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 1 11 2 8
|
4
|
|
2
|
4
1 8 8 8
|
6
|
|
3
|
2
7 6
|
0
|