Задача 2. Атака на боссов ≡

Условие

Вот он, момент истины! Мальчик Вова дошел в своей любимой игре до самого последнего уровня. На нем ему осталось последовательно победить n боссов. Сначала он должен победить босса под номером 1, затем под номером 2, затем 3, и так до номера n. Каждый босс имеет силу a_i. Для того, чтобы гарантированно победить босса, сила персонажа Вовы на данном шаге должна быть строго больше силы босса. Если Вова побеждает босса, то его сила увеличивается на силу побежденного босса.

Силы персонажа Вовы хватало на то, чтобы победить всех боссов, поэтому перед последним уровнем он решил передохнуть. Но проблема пришла откуда не ждали! На серверах игры произошел сбой, и у всех персонажей в игре обнулились силы. Вова очень расстроился этому, ведь он долго и упорно набирал силу, проходя все уровни. Сейчас ему придется по новой проходить уровни, чтобы набрать нужную силу. Но Вова не хочет проходить все уровни, поэтому он просит Вас написать программу, которая определит, какое минимальное количество силы Вове нужно набрать, чтобы гарантированно победить всех боссов.

Формат входных данных

В первой строке записано целое число n - количество боссов.

Во второй строке записано n целых чисел a_i - силы боссов.

Формат выходных данных

Выведите одно целое число - минимальное необходимое количество силы, чтобы победить всех боссов.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ a_i ≤ 10⁹

Система оценки и описание подзадач

Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

5
2 5 8 4 6

4