Даны \(n\) башен из кубиков, пронумерованных от \(1\) до \(n\). В \(i\)-й башне \(a_i\) кубиков.
За один ход можно переложить один кубик с \(i\)-й башни на \(j\)-ю, но только если \(a_i > a_j\). Такой ход увеличивает \(a_j\) на \(1\) и уменьшает \(a_i\) на \(1\). Вы можете сделать сколько угодно ходов (возможно, ноль).
Какое наибольшее количество кубиков можно получить на башне \(1\) после ходов?
Выходные данные
На каждый набор входных данных выведите наибольшее количество кубиков, которые могут оказаться на башне \(1\) после того как вы сделаете произвольное количество ходов (возможно, ноль).
Примечание
В первом наборе входных данных вы можете переместить кубик с башни \(2\) на башню \(1\), сделав количества кубиков равными \([2, 1, 3]\). Затем переместить кубик с башни \(3\) на башню \(1\), сделав количества кубиков равными \([3, 1, 2]\). Башня \(1\) высотой \(3\) кубика, и нельзя получить больше.
Во втором наборе входных данных можно переместить кубик с любой из башен \(2\) или \(3\) на башню \(1\) так, чтобы в ней стало \(2\) кубика.
В третьем наборе входных данных можно \(500000000\) раз переместить кубик с башни \(2\) на башню \(1\). После этого количества кубиков станут \([500000001, 500000000]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 2 3
3
1 2 2
2
1 1000000000
10
3 8 6 7 4 1 2 4 10 1
|
3
2
500000001
9
|