B. Caisa и колонны
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Caisa уже купил сахар и теперь идет домой. Во время пути домой он решил пройти игру на своем мобильном телефоне.

В игре есть (n + 1) колонн, пронумерованных от 0 до n. Нулевая колонна имеет высоту 0, i(i > 0) колонна имеет высоту hi. Цель игры — добраться до n-й колонны, при этом единственное действие, которое может совершать игрок: перепрыгнуть с текущей колонны (обозначим ее номер переменной k) на следующую колонну (ее номер равен k + 1). После описанного прыжка энергия игрока увеличивается на hk - hk + 1 (если это значение меньше нуля, то игрок теряет соответствующее количество энергии). По правилам игры в любой момент времени энергия игрока должна быть неотрицательной.

Изначально Caisa стоит на нулевой колонне и имеет ноль единиц энергии. Также в игре есть специально оплачиваемая возможность: за один доллар игрок может увеличить высоту любой колонны на единицу. Caisa может использовать эту возможность несколько раз, но, конечно, он не хочет тратить слишком много денег. Какое минимальное количество денег ему придется потратить, чтобы пройти игру?

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 105). В следующей строке записаны n целых чисел h1, h2, ..., hn (1  ≤  hi  ≤  105), обозначающие высоты колонн.

Выходные данные

Выведите единственное целое число — минимальное количество денег, которое придется заплатить Caisa, чтобы пройти игру.

Примеры
Входные данные
5
3 4 3 2 4
Выходные данные
4
Входные данные
3
4 4 4
Выходные данные
4
Примечание

В первом тестовом примере Caisa должен заплатить 4 доллара и увеличить высоту нулевой колонны на 4. В таком случае он сможет пройти игру.