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

Автор:Иван Кобец   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

1 ≤ ai ≤ 109

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
nai
1501 ≤ n ≤ 10001 ≤ ai ≤ 1000полная
2501 ≤ n ≤ 1051 ≤ ai ≤ 1091полная

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

Стандартный вход Стандартный выход
1
5
2 5 8 4 6
4

0.105s 0.021s 15