Wstęp do programowania w C++

Kolumny mrówek

Jeśli myślicie, że mrówki poruszają się w chaotyczny sposób, nic bardziej mylnego. Na mrówczych drogach panuje ład i porządek. Nie ma tam zjawiska wyprzedzania. Jeśli szybsza mrówka napotka mrówkę wolniejszą, zwalnia i dotrzymuje jej kroku. W ten sposób powstają kolumny mrówek, poruszających się z jednakową prędkością. Dzięki temu mrówki poruszają się względnie szybko.

A teraz zadanie. Jest n pracowitych mrówek. Mrówki przemieszczają się po szlaku w jednym kierunku. Każda mrówka rozpoczyna w innym punkcie szlaku, ale niektóre mrówki poruszają się z różnymi prędkościami. Kiedy szybsza mrówka napotka mrówkę wolniejszą, zwalnia i dotrzymuje jej kroku, stając się częścią tej samej kolumny mrówek. Po pewnym czasie liczebność takich kolumn będzie niezmienna. No i to właśnie jest przedmiotem tego problemu. Ile kolumn mrówek powstanie?
Zakładamy, że jedna samotnie maszerująca mrówka to także kolumna.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita n (1 ≤ n ≤ 100 000) oznaczająca liczbę mrówek. Kolejne n wierszy zawiera początkową pozycję i prędkość pojedynczej mrówki. Pozycja jest nieujemną liczbą całkowitą, a prędkość to liczba całkowita dodatnia. Obie wartości nie przekraczają 10⁹. Wszystkie mrówki rozpoczynają wędrówkę z innej pozycji, które są podane w porządku rosnącym na wejściu. Zakładamy, że szlak jest tak długi, że ho, ho.

Wyjście
Na wyjściu należy podać liczbę powstałych kolumn mrówek.

Przykład

Wejście
5
0 1
1 2
4 3
7 2
9 1

Wyjście
2