레모네이드 줄서기

면접 대비

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

요약

각 소가 견딜 수 있는 최대 대기 인원이 주어질 때, 줄에 남는 소의 수가 최소가 되도록 도착 순서를 정한다.

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

문제

무더운 여름날, 농부 존이 소 $N$ 마리에게 레모네이드를 나눠 주려고 한다. 소는 모두 레모네이드를 좋아하지만 좋아하는 정도는 저마다 다르다. $1$ 번부터 $N$ 번까지 번호가 붙어 있고, $i$ 번 소는 자기 앞에 최대 $w_i$ 마리까지 서 있어야 줄을 서서 기다린다.

지금 소는 모두 들판에 있다. 존이 종을 울리면 소들은 곧바로 레모네이드 가판대로 몰려온다. 존이 레모네이드를 나눠 주기 전에 소가 모두 도착하고, 두 소가 같은 시각에 도착하는 일은 없다. $i$ 번 소는 도착한 순간 줄에 서 있는 소가 $w_i$ 마리 이하이면 줄을 서고, 그보다 많으면 그냥 돌아간다.

존은 레모네이드를 미리 준비하려 하지만 낭비하고 싶지는 않다. 줄을 서는 소의 수는 도착 순서에 따라 달라진다. 가능한 모든 도착 순서를 따질 때 줄을 서는 소가 가장 적은 경우의 마릿수를 구하여라.

입력

첫째 줄에 $N$ 이 주어진다. 둘째 줄에 $N$ 개의 정수 $w_1, w_2, \dots, w_N$ 이 공백으로 구분되어 주어진다. $1 \leq N \leq 10^5$ 이고, 각 소에 대해 $0 \leq w_i \leq 10^9$ 이다.

출력

가능한 모든 도착 순서 가운데 줄을 서는 소가 가장 적은 경우의 마릿수를 한 줄에 출력한다.

힌트

첫 번째 예제에서는 세 마리만 줄을 서고, 이보다 적게 만드는 순서는 없다. $w$ 가 $7$ 인 소와 $400$ 인 소가 먼저 도착해 줄을 선다고 하자. 이어서 $w$ 가 $1$ 인 소가 도착하지만 이미 두 마리가 서 있어 돌아간다. 마지막으로 $w$ 가 $2$ 인 소 두 마리가 도착해 한 마리는 줄을 서고 한 마리는 돌아간다.

예제4

예제 1
입력
```
5
7 1 400 2 2
```
예상 출력
```
3
```
예제 2
입력
```
1
0
```
예상 출력
```
1
```
예제 3
입력
```
6
0 0 0 0 0 0
```
예상 출력
```
1
```
예제 4
입력
```
8
0 1 2 3 4 5 6 7
```
예상 출력
```
4
```