Kəsiklər
Heç iki kəsik ortaq nöqtəyə malik olmamalıdır. Həmçinin ortaq tire də olmamalıdır.
Teleqrafçılar üçün təlimat
Kəsiklər Geometriyası İnstitutunun (KİG) direktoru Aazı öz kabinetində qəbul etdi. İnstitutun vəziyyəti yaxşı görünürdü, lakin problem başqa bir yerdə idi.
Biz daim məşğuluq. Proqramlaşdırma çempionatlarının mövsümü başladıqda, yarış təşkilatçılarının sifarişi ilə iki kəsiyin kəsişməsi ilə bağlı çoxlu məsələlər həll edirik. Lakin bu işlər artıq rutin hal alıb və əməkdaşlar maraqlarını itirməyə başlayırlar. Bəzi yerlərdə hətta iş əvəzinə özfəaliyyətlə məşğul olurlar - şam işığında bayan konsertləri təşkil edirlər. Bizim üçün bu məsələdən fərqli, amma ona bənzər bir məsələ formalaşdıra bilərsinizmi?
Məsələn... Düz xətt üzərində n kəsik verilib. Hər bir kəsik üçün onunla ən azı bir ortaq nöqtəyə malik olan kəsiklərin sayını hesablamaq lazımdır.
KİG əməkdaşları bu məsələyə böyük maraq göstərdilər. Üstəlik, bu məsələnin həlli üçün proqramı yazmağı sizə həvalə etdilər.
Giriş məlumatları
Bir və ya bir neçə testdən ibarətdir. Hər testin ilk sətirində kəsiklərin sayı n (1 ≤ n ≤ 10^5) verilir. Növbəti n sətir kəsikləri təsvir edir; i-ci sətir L[i] və R[i] tam ədədlər cütlüyünü - i-ci kəsiyin başlanğıc və son koordinatlarını (-10^9 ≤ L[i] ≤ R[i] ≤ 10^9) ehtiva edir. Giriş məlumatları üzrə n dəyərlərinin ümumi cəmi 10^5-i keçmir. Giriş məlumatları sıfırla tamamlanır. Testlərin sayı 10^4-ü keçmir.
Çıxış məlumatları
Hər test üçün bir sətirdə n ədəd çıxarın, nümunədə göstərildiyi kimi: i-ci ədəd - i-ci kəsiklə ən azı bir ortaq nöqtəyə malik olan kəsiklərin sayı, özünü saymadan. Çıxış formatına maksimum dərəcədə riayət edin.