의심 많은 젖소

Farmer John의 젖소는 $N$마리($1 \le N \le 100{,}000$)이며, 각 젖소는 자신의 우유 생산량을 신경 쓴다. 우유를 많이 생산하지 못하는 젖소는 다른 젖소에게 놀림을 받기 쉽다.

FJ는 젖소마다 착유 시간 구간 $[A_i, B_i]$($0 \le A_i < B_i \le 1{,}000{,}000{,}000$)을 배정한 일정표를 짰다. 젖소 $i$($1 \le i \le N$)는 시각 $A_i$에 착유를 위해 외양간에 들어오고, 시각 $B_i$에 외양간을 나간다. 외양간 문은 좁아서 한 번에 한 마리만 지나갈 수 있으므로, FJ는 두 젖소가 같은 시각에 들어가거나 나오지 않도록 일정을 짰다.

젖소 $i$의 구간이 젖소 $j$의 구간을 포함하면, 즉 $A_i < A_j < B_j < B_i$이면 두 구간이 중첩되었다고 한다. 중첩은 좋지 않다. 젖소 $i$는 젖소 $j$가 착유하는 내내 외양간에 있게 되어 젖소 $j$를 훔쳐보고 우유 생산량을 알아낼 수 있다. 젖소들은 자신의 생산량이 다른 젖소에게 알려지는 것을 원하지 않으므로, FJ는 일정표에 중첩 구간이 없기를 바란다.

FJ를 도와 젖소 $1$부터 $K$까지의 구간에 중첩이 전혀 없도록 하는 가장 큰 $K$($1 \le K \le N$)를 구하라.