두 무대의 공연 편성

문제

공연장에 무대가 두 개 있다. 다음 축제 기간에 열고 싶다고 신청한 공연이 N건 들어왔고, i번째 공연은 시각 s_i에 시작해 시각 e_i에 끝난다. 항상 s_i < e_i이다. 한 무대에서는 동시에 공연을 하나만 열 수 있다. 어떤 공연이 끝나는 시각에 같은 무대에서 다른 공연이 시작하는 것은 허용된다. 즉 같은 무대에 배정된 두 공연의 구간 [s, e)가 서로 겹치지 않으면 된다. 공연은 한 번 열기로 하면 두 무대 중 한 곳에서 처음부터 끝까지 열려야 하고, 도중에 무대를 옮길 수 없다. 신청된 공연 중 일부는 열지 않아도 된다. 무대 두 개를 모두 활용해 열 수 있는 공연의 최대 개수를 구하시오. 처음에는 두 무대 모두 비어 있고, 어느 시각에든 공연을 시작할 수 있다. 같은 구간의 공연이 여러 건 신청될 수도 있으며, 이 경우에도 각각 별개의 공연으로 센다.

입력

첫 줄에 정수 N이 주어진다. 다음 N개의 줄에 i번째 공연의 s_i와 e_i가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 0 ≤ s_i < e_i ≤ 10^9이다. 모든 값은 정수이다.

출력

열 수 있는 공연의 최대 개수를 정수 하나로 출력한다.

5
1 4
2 6
3 5
5 8
6 9

4

3
1 3
1 3
1 3

2

1
0 1

1

출처: Devin.KR 자체 제작