19700번 - 수업

문제

숭실대학교의 권욱제 교수는 새로운 강의를 준비하고 있다. 강의하기 귀찮은 권욱제 교수는 팀플 과제를 던져주고 대충 발표를 들으면서 한 학기 수업을 치우려고 한다. 그래서 수강생 $N$명을 몇 개의 팀으로 나누려고 한다. 그러나, 수강생들의 자존심이 세다. $i$번째 수강생은 팀원들 중 자신보다 키가 큰 사람이 $k_i$명 이상이면 강의실을 박차고 나갈 거라고 했다.

마음이 여린 권욱제 교수는 모든 수강생의 요구를 만족하도록 모든 수강생을 각각 하나의 팀에 넣으려 한다. 최소 몇 개의 팀을 만들어야 할까?

입력

첫 줄에 학생의 수 $N$이 주어진다.

이후 $N$개의 줄에 각 학생의 키 $h_i$와 최소 등수 $k_i$가 주어진다.

학생들의 키는 모두 다르다.

출력

만들어야 하는 팀의 개수의 최솟값을 출력한다.

제한

• 1ドル \le N \le 500,000$
• 1ドル \le h_i \le 500,000,ドル 1ドル \le k_i \le N$

힌트