Masala E

Fermada \(N\) ta tovuq mavjud va ular bir chiziqdagi kataklarga joylashtirilgan, bunda \(i-\) tovuq \(i-\) katakda yashaydi. Tovuqlar noyob va ular vaqti-vaqti bilan noyob "oltin tuxum" qo'yadi. Tovuqxona egasi hech qaysi tuxumga ziyon yetishini xohlamaydi, shuning uchun u mini-robotlar sotib olishga qaror qildi. Robot tovuq tuxum qo'ygan zahoti uni ehtiyotkorlik bilan tutib oladi hamda avaylab savatga joylashtiradi. Mini-robot har sekundda ko'pi bilan 1 katak yura oladi. Robot narxi juda qimmat, shuning uchun fermer imkon qadar kamroq robot yordamida barcha tuxumlarni yig‘ib olishni xohlaydi.

Biz har bir tovuq qachon tuxum qo'yishini bilamiz: \(s_i-\)katakdagi tovuq, \(t_i​-\)sekundda oltin tuxum qo'yadi. Robotlarning dastlabki joylashuvini erkin belgilagan holda, barcha tuxumlarni tutib olish uchun kamida nechta robot kerak bo‘lishini aniqlang.

Birinchi qatorda \(N \ (1 \le N \le 200 \ 000)\) — tuxumlar soni kiritiladi.

Keyingi \(N\) qatorda har bir tuxum uchun ikkita son: \(s_i\)​ va \(t_i\)​ \( (1 \le s_i, t_i \le 10^9)\).

Har bir tovuq bir vaqtda ko'pi bilan bitta tuxum qo'ya oladi, aniqroq aytganda barcha \(i \neq j\) uchun \(s_i \neq s_j\) yoki \(t_i \neq t_j\) ekanligi kafolatlanadi.

Yagona qatorda — kerakli minimal robotlar soni \(w\) ni chop eting.