B. Ресторан

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ресторан $n$ ширхэг түрээсийн захиалга авчээ. Түрээс бүр тодорхой тасралтгүй хугацаанд үргэлжлэх ба $i$-дэх захиалга нь $l_{i}$ хугацаанд эхлэн $r_{i}$ хугацаанд дуусна ($l_{i} ≤ r_{i}$).

Ресторан захиалгыг зөвшөөрч эсвэл зөвшөөрөхгүй байж болно. Тэгвэл ресторан хамгийн олондоо хэчнээн захиалгыг зөвшөөрч чадах вэ?

Аль ч хоёр зөвшөөрөгдсөн захиалгын үргэлжлэх хугацаа нь хормын төдийд ч огтлолцож болохгүй. Ямар нэгэн агшинд нэг захиалга нь дуусчихсан, нөгөө захиалга нь эхэлж байвал уг хоёр захиалга хоёул зөвшөөрөгдөж болно.

Оролт

Эхний мөрөнд захиалгын тоо болох $n$ ($1 ≤ n ≤ 5*10^{5}$) байна. Дараагийн $n$ мөрөнд $l_{i}$ ба $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ 10^{9}$) тоонууд байна.

Гаралт

Зөвшөөрч болох захиалгуудын хамгийн их утгыг хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
2
7 11
4 7
Гаралт
1
Оролт
5
1 2
2 3
3 4
4 5
5 6
Гаралт
3
Оролт
6
4 8
1 5
4 7
2 5
1 3
6 8
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...