Problem V
Interval Scheduling

A set of $8$ intervals corresponding to sample input 2. The maximum number of nonoverlapping intervals is $3$, achieved by the highlighted intervals.

Consider a set of $n$ intervals $I_1,\dots ,I_n$, each given as an integer tuple $(s_i,f_i)$ with $s_i<f_i$, such that the $i$th interval starts at $s_i$ and ends at $f_i$. We want to determine the maximum number of nonoverlapping intervals. More formally, we want to determine the size of a largest subset $S\subseteq \{1,\dots ,n\}$ such that for $i,j\in S$ with $i\ne j$ we have $f_j\le s_i$ or $f_i\le s_j$. Note that the intervals $[1,2]$ and $[2,3]$ are not considered to be overlapping.

Input

The first line of input consists of an integer $n\in \{1,\dots ,{10}^5\}$, the number of intervals. Each of the following $n$ lines consists of two space-separated integers $s$ and $f$, indicating an interval starting at $s$ and ending at $f$, with $0\le s<f\le {10}^9$.

Output

Output a single integer, the largest number of nonoverlapping intervals.

3
1 4
2 8
5 9

2

8
0 6
1 4
3 5
3 8
4 7
5 9
6 10
8 11

3