Background

정렬된 구간 중 서로 겹치지 않게 선택할 수 있는 최대 개수를 계산한다.

Description

$N$개의 일정이 주어진다. 각 일정 $i$는 시작 시각 $S_i$와 종료 시각 $T_i$로 표현된다.

두 일정을 모두 선택하려면, 한 일정이 끝난 뒤에 다음 일정이 시작되어야 한다. 즉, 이전에 선택한 일정의 종료 시각이 $t$라면 시작 시각이 $t$ 이상인 일정은 이어서 선택할 수 있다.

시작 시각과 종료 시각이 같은 일정도 선택할 수 있으며, 이 일정은 시작하자마자 끝나는 것으로 본다.

선택할 수 있는 일정의 최대 개수를 구하여라.

Format

Input

첫째 줄에 일정의 개수 $N$이 주어진다.

다음 $N$개의 줄에는 두 정수 $S_i$와 $T_i$가 공백으로 구분되어 주어진다.

입력은 다음 조건을 만족한다.

$1 \leq N \leq 100000$

$0 \leq S_i \leq T_i \leq 2147483647$

Output

서로 겹치지 않게 선택할 수 있는 일정의 최대 개수를 출력한다.

Samples

8
0 0
0 3
1 2
2 2
2 5
3 4
4 4
4 7

6

7
1 10
2 3
3 4
4 8
8 9
9 9
9 12

6

Limitation

3s, 256MiB for each test case.