극한직업: 영양사 선생님

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

요약

학생들을 원하는 순서로 줄 세울 때, 같은 시점에 자리에 앉아 있는 최대 인원을 구합니다.

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

문제

급식 시간이 시작되었다!

학생 $N$ 명이 한 줄로 서서 배식을 받고 급식실에 앉는다. 배식은 $1$ 분 만에 끝나고, 모든 학생은 배식이 끝나자마자 급식실 자리에 앉는다. 즉, 줄의 맨 앞에서 $i (1 \leq i \leq N)$ 번째에 있는 학생은 급식 시간이 시작된 지 $i$ 분 만에 자리에 앉는다.

학생마다 밥을 먹는 데 걸리는 시간도 정해져 있다. 어떤 학생이 $A$ 분에 자리에 앉았고 $B$ 분 동안 밥을 먹는다면, 그 학생은 급식 시간이 시작된 지 $A$ 분, $A+1$ 분, $\cdots$ , $A+B-1$ 분이 지난 시점에는 앉아 있고, $A+B$ 분이 지난 시점에 자리에서 일어나 급식실을 떠난다.

대곽이는 모든 학생과 친하기 때문에 원하는 순서대로 줄을 세울 수 있다. 대곽이는 각 학생이 밥을 먹는 데 걸리는 시간을 알고 있는데, $i (1 \leq i \leq N)$ 번째 학생은 $b_i$ 분 동안 밥을 먹는다.

어떤 줄 세우기 순서에서, 임의의 양의 정수 $t$ 에 대해 급식 시간이 시작된 지 $t$ 분이 지난 시점에 자리에 앉아 있는 학생 수를 혼잡도라고 한다. 정확히 $t$ 분이 지난 시점에 일어나는 학생은 세지 않는다.

장난을 좋아하는 대곽이는 영양사 선생님을 정신없게 만들려고 모든 학생을 적당한 순서로 세워서 혼잡도가 최대한 커지도록 하고 싶다. 대곽이가 만들 수 있는 최대 혼잡도를 구해보자.

입력

첫째 줄에는 학생의 수를 나타내는 양의 정수 $N$ 이 주어진다. $(1 \leq N \leq 300\,000)$

둘째 줄에는 각 학생이 밥을 먹는 시간을 나타내는 $N$ 개의 양의 정수 $b_i$ 가 공백으로 구분되어 주어진다. $(1 \leq b_i \leq 1\,000\,000\,000)$

출력

대곽이가 만들 수 있는 최대 혼잡도를 나타내는 정수 하나를 출력한다.

예제3

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