스마트 홈의 점검 시간표

문제

스마트 홈의 제어기는 밤 동안 여러 기기의 자동 점검을 진행한다. 점검에는 공용 통신 회선을 사용하므로 한 시간 칸에는 기기 하나만 점검할 수 있다. 시간 칸에는 1부터 시작하는 연속된 정수 번호가 붙어 있다. 모든 기기의 점검 준비는 첫 번째 시간 칸이 시작하기 전에 끝나 있으며, 각 기기의 점검은 정확히 한 칸을 사용한다. 한번 시작한 점검은 그 칸 안에서 끝나고, 다음 칸으로 나누어 진행할 수 없다. 각 기기에는 점검 마감 번호가 하나씩 정해져 있다. 마감 번호가 d인 기기는 1번부터 d번까지의 시간 칸 중 하나에서 점검해야 한다. d번 칸에서 점검을 마쳐도 마감을 지킨 것으로 인정한다. 마감 번호가 0인 기기는 사용할 수 있는 시간 칸이 없으므로 이번 밤에는 점검할 수 없다. 기기마다 마감 번호가 다를 수 있고, 여러 기기가 같은 마감 번호를 가질 수도 있다. 같은 마감 번호를 가진 기기들도 서로 다른 기기다. 제어기는 입력에 주어진 순서와 관계없이 기기의 점검 순서를 자유롭게 정할 수 있다. 모든 기기를 반드시 점검할 필요는 없으며, 선택하지 않은 기기의 점검은 다음 날로 미룬다. 어떤 기기를 점검하더라도 완료한 기기 수에는 똑같이 1이 더해진다. 기기의 종류나 마감이 빠르다는 이유로 추가 점수를 주지는 않는다. 또한 하나의 기기를 여러 번 점검하여 완료 수를 늘릴 수는 없다. 이번 밤에 마감을 지키면서 점검할 수 있는 기기 수의 최댓값을 구한다. 최댓값을 만드는 시간표가 여러 개일 때는 어느 시간표를 택해도 되며, 실제 시간표나 선택한 기기 번호는 출력하지 않는다. 점검할 수 있는 기기가 하나도 없으면 완료할 수 있는 기기 수는 0이다.

입력

첫째 줄에 기기 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 30,000이다.
둘째 줄에 각 기기의 마감 번호를 나타내는 정수 d_1, d_2, …, d_N이 공백으로 주어진다. 0 ≤ d_i ≤ 30,000이다.

출력

마감을 지키면서 점검할 수 있는 기기 수의 최댓값을 정수 하나로 출력한다.

6
1 1 3 0 2 3

3

4
0 0 0 0

0

5
5 2 5 1 5

5

출처: Devin.KR 자체 제작