맥시마이저 최소화

어떤 회사가 맥시마이저(Maximizer) 라는 새로운 정렬 장치를 만들고 있습니다. 맥시마이저에는 $1$번부터 $n$번까지 번호가 매겨진 $n$개의 입력이 있고, 각 입력에는 정수 하나가 놓입니다. 출력은 하나뿐이며, 항상 입력들에 놓인 값들의 최댓값과 같아야 합니다.

맥시마이저는 정렬기 $\text{Sorter}(i_1, j_1), \ldots, \text{Sorter}(i_k, j_k)$ 들을 순서대로 이어 붙인 파이프라인으로 구현됩니다. 각 정렬기는 $n$개의 입력과 $n$개의 출력을 가집니다. $\text{Sorter}(i, j)$ 는 $i, i+1, \ldots, j$ 위치의 값들을 비내림차순으로 정렬하고, 나머지 위치의 값은 그대로 통과시킵니다. 마지막 정렬기의 $n$번째 출력이 맥시마이저의 출력이 됩니다.

한 엔지니어가, 파이프라인에서 일부 정렬기를 제거해도 맥시마이저가 모든 가능한 입력에 대해 여전히 올바른 결과를 낸다는 사실을 알아냈습니다. 주어진 파이프라인에서, 정렬기들의 원래 순서를 유지한 채 일부만 남겼을 때 모든 가능한 입력 값에 대해 여전히 올바른 결과를 내는 가장 짧은 부분 수열의 길이를 구하세요.

맥시마이저의 설명(정렬기들의 초기 파이프라인)을 읽어, 그러한 가장 짧은 부분 수열의 길이를 계산하여 출력하는 프로그램을 작성하세요.

첫째 줄에 두 정수 $n$과 $m$이 공백 하나로 구분되어 주어집니다 ($2 \le n \le 50\,000$, $1 \le m \le 500\,000$). $n$은 입력의 개수, $m$은 파이프라인에 있는 정렬기의 개수입니다.

이어지는 $m$개의 줄에는 파이프라인 순서대로 각 정렬기가 주어집니다. 그중 $k$번째 줄에는 $k$번째 정렬기의 매개변수인 두 정수 $i_k$와 $j_k$가 공백 하나로 구분되어 주어집니다 ($1 \le i_k < j_k \le n$).

모든 가능한 입력에 대해 여전히 올바른 결과를 내는, 초기 정렬기 파이프라인의 가장 짧은 부분 수열의 길이를 정수 하나로 한 줄에 출력하세요.