Садоводство в поезде

면접 대비

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

요약

하루에 한 개씩만 심을 수 있을 때, 모든 식물이 자라서 익는 날짜를 가장 앞당기는 심는 순서를 정하고 그 최소 일수를 구한다.

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

문제

Путь Восточного экспресса довольно долог, поэтому взятых продуктов не всегда хватает, чтобы накормить его пассажиров. Для этого было предусмотрено выращивание необходимых овощей и растений на территории поезда. Однако, для того, чтобы вырастить растения, их сначала надо посадить.

У Бука есть $n$ растений, $i$ -му из которых требуется $a\_i$ дней для роста и созревания. Из-за сильной загруженности, Бук не может сажать более одного растения в день, поэтому для него сильно важен порядок, в котором он будет сажать растения. Разумеется, он хочет, чтобы все растения созрели как можно раньше, чтобы как можно раньше их можно было начать использовать в приготовлении блюд. Помогите ему --- найдите минимальное количество дней, через которое все растения могут созреть при определенном порядке их высаживания.

입력

В первой строке содержится число $n$ --- количество растений, которое есть у Бука ( $1 \le n \le 10^5$ ).

В следующей строке содержится $n$ чисел $a\_i$ , которые означает количество дней, требуемое для роста и созревания $i$ -го растения ( $1 \le a\_i \le 10^9$ ).

출력

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

예제1

예제 1
입력
```
5
1 5 3 5 4
```
예상 출력
```
6
```