Вагоны Восточного Экспресса
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

За одну единицу времени проводник поезда может либо освободить целиком вагон, либо выпустить из каждого вагона, где еще остались люди, по одному человеку.

Пассажиры в спешке, проводник в панике, Ваша задача состоит в том, чтобы вычислить минимальное время, необходимое для высадки всех пассажиров поезда.

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

В первой строке входных данных содержится единственное целое число n — количество вагонов в поезде (1 ≤ n ≤ 105).

Во второй строке содержатся n целых чисел ai (0 ≤ ai ≤ 109), i-е из которых обозначает количество пассажиров в i-м вагоне.

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

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

Примеры

Входные данные
3
1 1 2
Выходные данные
2
Входные данные
5
10 20 100 100 100
Выходные данные
5