В поезде, который следует из Стамбула в Лондон, 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