기차 안에서 하는 원예

면접 대비

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

요약

하루에 한 개씩 n개의 식물을 심을 때, 마지막 식물이 익는 날을 가장 빠르게 만드는 값을 구합니다.

난이도: 쉬움10점 중 3점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

동방 특급 열차의 여정은 꽤 길어서, 싣고 온 식량만으로는 승객을 늘 먹이기 어렵다. 그래서 열차 안에서 채소와 식물을 기르도록 되어 있다. 다만 식물을 기르려면 먼저 심어야 한다.

북은 $n$ 개의 식물을 가지고 있다. $i$ 번째 식물이 자라서 익기까지 $a_i$ 일이 필요하다. 북은 업무가 많아서 하루에 한 개 이상의 식물을 심을 수 없으므로, 심는 순서가 중요하다. 북은 모든 식물을 되도록 일찍 익혀서 요리에 쓰고 싶어 한다. 어떤 심는 순서에 대해 모든 식물이 익을 때까지 걸리는 최소 일수를 구하라.

입력

첫 줄에 북이 가진 식물의 개수 $n$ 이 주어진다 ( $1 \le n \le 10^5$ ).

다음 줄에는 $n$ 개의 정수 $a_i$ 가 주어진다. $a_i$ 는 $i$ 번째 식물이 자라서 익는 데 필요한 날의 수이다 ( $1 \le a_i \le 10^9$ ).

출력

어떤 심는 순서에 대해 모든 식물이 자라서 익는 최소 일수를 한 줄에 출력한다.

예제1

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