Вагоны Восточного Экспресса

면접 대비

시간 제한2초메모리 제한1024 MB

요약

한 단위 시간에 빈 차량 하나를 통째로 비우거나 사람이 남은 모든 차량에서 한 명씩 내릴 수 있을 때, 모든 승객을 내리는 최소 시간을 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 수학, 이분 탐색
정답자: 아직 제출이 없습니다

문제

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

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

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

입력

В первой строке входных данных содержится единственное целое число $n$ --- количество вагонов в поезде $(1 \leq n \leq 10^5)$ .

Во второй строке содержатся $n$ целых чисел $a\_i$ $(0 \leq a\_i \leq 10^9)$ , $i$ -е из которых обозначает количество пассажиров в $i$ -м вагоне.

출력

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

예제2

예제 1
입력
```
3
1 1 2
```
예상 출력
```
2
```
예제 2
입력
```
5
10 20 100 100 100
```
예상 출력
```
5
```