34156번 - 테토와 바게트 서브태스크

문제

카사네 테토(重音テト)는 바게트를 좋아한다! 그래서 오늘도 바게트를 먹으려고 한다. 테토는 한 입에 바게트를 모두 삼킬 수 없어서, 바게트를 최소 한 번씩 잘라서 먹으려고 한다.

바게트 $N$개가 수직선 위에 놓여 있고, 이 중 $i(1 \le i \le N)$번째 바게트는 $[s_i, ,円 e_i]$ 구간에 위치한다. 1ドル \le i < j \le N$을 만족하는 모든 $i,,円 j$에 대해 $s_i=s_j,,円 e_i=e_j$를 동시에 만족하는 경우는 없고, 바게트의 길이 $e_i − s_i$는 2ドル$ 이상이다. 바게트 $A$가 바게트 $B$에 포함된다는 것은 $s_B \le s_A$와 $e_A \le e_B$를 동시에 만족하는 경우를 말한다. 테토는 바게트 $A$가 바게트 $B$에 포함되었다고 판단하면, 포함된 바게트 $A$를 쓸모없다고 보고, 먹지 않는다. 테토는 정수 위치 $x(0 \le x \le 10^9)$에서 바게트를 자를 수 있으며, $s_i < x < e_i$를 만족하는 모든 바게트가 한 번의 칼질로 잘린다.

테토는 쓸모없는 바게트를 모두 제외하고 남은 모든 바게트를 먹을 생각이다. 먹을 바게트가 모두 한 번 이상 잘리도록 칼질을 해야 하는데, 바게트를 자르는 것은 매우 힘든 일이므로 되도록이면 칼질을 적게 하고 싶다. 테토는 승원이에게 최소 몇 번 칼질을 해야 하는지를 물어봤다. 하지만, 승원이는 연구 보고서를 작성하느라 바쁘므로 여러분이 대신 답해주자.

입력

첫 번째 줄에 바게트의 개수를 나타내는 정수 $N$이 주어진다. (1ドル \leq N \leq 1 ,円 000 ,円 000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에는 $i$번째 바게트의 시작 위치 $s_i$와 끝 위치 $e_i$를 나타내는 정수가 공백으로 구분되어 주어진다. (0ドル \leq s_i < e_i \leq 10^9,ドル $e_i - s_i \geq 2$)

출력

테토가 쓸모 없는 바게트를 제외한 모든 바게트를 모두 한 번씩은 자르기 위한 칼질의 최소 횟수를 출력하라.

제한

서브태스크

노트

입출력의 양이 많으므로, 빠른 입출력을 사용하는 것을 권장합니다. 다음은 대표적인 언어에서 빠른 입출력을 이용하는 방법입니다.

• C++: cin, cout을 사용한다면 main 함수 첫 줄에 std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(false);를 추가하고, 줄바꿈 시 std::endl 대신 '\n'을 출력해주세요. 이 경우 scanf를 비롯한 C의 입출력 함수는 사용할 수 없음에 유의해 주세요.
  • scanf/printf는 충분히 빠르므로 별도의 처리를 하지 않아도 괜찮습니다.
• Java: Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용해 주세요.
• Python3, PyPy3: input() 대신 sys.stdin.readline().rstrip()을 사용해 주세요.