Description

Given a set of $n$ activities $E=\{1,2,..,n\}$, where each activity requires the use of a common resource, such as a lecture hall, and only one activity can use the resource at any given time. Each activity $i$ has a start time $s_i$ and an end time $f_i$ for using the resource, with $s_i < f_i$. If activity $i$ is selected, it occupies the resource during the time interval $[s_i, f_i)$. The intervals $[s_i, f_i)$ and $[s_j, f_j)$ are said to be compatible if they do not overlap, i.e., when $f_i \leq s_j$ or $f_j \leq s_i$. The task is to select the largest subset of mutually compatible activities.

Input Format

The first line contains an integer $n$;

The next $n$ lines each contain two integers $s_i$ and $f_i$.

Output Format

Output the maximum number of mutually compatible activities.

Sample 1

4
1 3
4 6
2 5
1 7

2

Constraints & Hints

$1 \leq n \leq 1000$