Minimizing Maximizer

A company is building a new sorting device called Maximizer. The Maximizer has $n$ inputs numbered from $1$ to $n$; each input carries one integer. It has a single output that must always equal the maximum of the values on its inputs.

The Maximizer is implemented as a pipeline of sorters $\text{Sorter}(i_1, j_1), \ldots, \text{Sorter}(i_k, j_k)$. Every sorter has $n$ inputs and $n$ outputs. $\text{Sorter}(i, j)$ sorts the values on positions $i, i+1, \ldots, j$ into non-decreasing order and passes every other position through unchanged. The $n$-th output of the last sorter is the output of the Maximizer.

An engineer noticed that some sorters can be removed from the pipeline while the Maximizer still produces the correct result for every possible input. Determine the length of the shortest subsequence of the given pipeline (keeping the sorters in their original order) that still produces the correct result for all possible input values.

Write a program that reads the description of a Maximizer (its initial pipeline of sorters), computes the length of the shortest such subsequence, and writes that length.

The first line contains two integers $n$ and $m$ ($2 \le n \le 50\,000$, $1 \le m \le 500\,000$) separated by a single space, where $n$ is the number of inputs and $m$ is the number of sorters in the pipeline.

Each of the next $m$ lines describes one sorter in pipeline order. The $k$-th of these lines contains two integers $i_k$ and $j_k$ ($1 \le i_k < j_k \le n$) separated by a single space, the parameters of the $k$-th sorter.

Print a single line containing one integer: the length of the shortest subsequence of the initial pipeline of sorters that still produces correct results for all possible inputs.