Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_09_12 - Kolumny mrówek

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ą 109. 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


Dodane przez:Mariusz Śliwiński
Data dodania:2018-05-21
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.