먹이사슬

1부터 N까지 번호가 붙은 서로 다른 동물 N마리가 있다. 각 동물은 같은 수평선 위의 연속된 구간에서 활동하며, 이 구간을 그 동물의 활동 영역이라고 한다.

동물 i의 활동 영역이 (x1, x2), 동물 j의 활동 영역이 (x3, x4)일 때, 다음 중 하나가 성립하면 i가 j보다 먹이사슬에서 위에 있다고 한다.

• x1 < x3 이고 x2 > x4
• x1 = x3 이고 x2 > x4
• x1 < x3 이고 x2 = x4

즉 i의 활동 영역은 j의 활동 영역을 포함하며, 두 영역이 완전히 같지는 않다.

어떤 동물 집단을 한 줄로 나열했을 때, 앞에 놓인 각 동물이 뒤에 놓인 모든 동물보다 먹이사슬에서 위에 있으면 그 집단은 먹이사슬 구조를 가진다. 동물이 하나뿐인 집단도 먹이사슬 구조를 가진다. 집단의 크기는 그 안에 속한 동물의 수이다.

모든 동물의 활동 영역이 주어질 때, 먹이사슬 구조를 가지는 동물 집단의 가능한 최대 크기를 구하시오.

첫째 줄에 동물의 수 N (1 ≤ N ≤ 500,000)이 주어진다.

이어지는 N개의 줄에는 동물 번호, 활동 영역의 왼쪽 위치 L, 오른쪽 위치 R이 공백으로 구분되어 주어진다. L과 R은 1 이상 1,000,000,000 이하의 양의 정수이다. 동물 번호는 입력을 구분하기 위한 값이며, 답은 활동 영역으로 결정된다.

먹이사슬 구조를 가지는 동물 집단의 최대 크기를 출력한다.