시장 선거 포스터
시간 제한1초메모리 제한192 MB
긴 벽에 순서대로 겹쳐 붙이는 n개의 포스터 중, 이후 포스터에 완전히 가려지지 않고 일부라도 보이는 포스터의 수를 구합니다.
문제
마을에서 시장 선거를 앞두고 후보자들의 포스터를 벽에 붙이려고 한다. 선거 관리 위원회는 다음 규칙을 정했다.
- 각 후보자는 포스터를 정확히 하나만 붙일 수 있다.
- 모든 포스터의 높이는 벽의 높이와 같고, 너비는 후보자가 정할 수 있다.
- 벽은 byte 단위의 조각으로 나뉘어 있다.
- 각 포스터는 주어진 벽 구간을 빈틈없이 덮어야 한다.
벽의 너비는 100,000,000 byte이다. 후보자들은 입력으로 주어진 순서대로 포스터를 붙이며, 이미 포스터가 붙어 있는 구간에도 새 포스터를 그 위에 붙일 수 있다. 모든 포스터를 붙인 뒤 선거 전날 벽에서 적어도 일부가 보이는 포스터가 몇 개인지 구하라.
입력
첫 줄에 포스터의 개수 n이 주어진다. 1 ≤ n ≤ 10,000.
다음 n줄에는 각 포스터가 덮는 구간의 왼쪽 끝과 오른쪽 끝 위치 l, r이 주어진다. 1 ≤ l < r ≤ 100,000,000.
포스터는 입력된 순서대로 붙인다.
출력
입력 순서대로 모든 포스터를 붙인 후, 벽에서 보이는 포스터의 총 개수를 출력한다.