Problem G
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,\ldots , 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,\ldots ,n\} $ such that for $i, j\in S$ with $i\neq j$ we have $f_ j \leq s_ i$ or $f_ i\leq 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,\ldots , 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\leq s<f\leq 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