eolymp
bolt
Try our new interface for solving problems
Məsələlər

Задача от Степана

Задача от Степана

Zaman məhdudiyyəti 0.75 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Перебирая свои детские игрушки, Степан нашел набор из N разных прямоугольников и вспомнил задачу, которую ему когда-то задавал старенький учитель математики. Назовём прямоугольник маленьким, если найдётся другой прямоугольник из заданного набора, которым можно полность накрыть этот прямоугольник. При этом прямоугольники можно поворачивать, но соответствующие стороны должны быть параллельны.

Например, прямоугольник со сторонами 1 и 10 можно полностью накрыть прямоугольником 10 и 3, но нельзя накрыть прямоугольником со сторонами 9 и 9. Прямоугольники со сторонами 10 и 3, а также со сторонами 9 и 9 накрыть нельзя, соответственно в наборе из этих трёх прямоугольников только один маленький. Напишите программу, которая решит вспомненную Степаном задачу – определит количество маленьких прямоугольников в заданном наборе.

Giriş verilənləri

Первая строка входного файла содержит одно целое число N (2N200000). В каждой из последующих N строк содержится два целых положительных числа – размеры одного прямоугольника. Все размери не превышают 1000000. Среди заданных прямоугольников нет одинаковых.

Çıxış verilənləri

Выходной файл должен содержать одно целое число - количество маленьких прямоугольников в заданном наборе.

Nümunə

Giriş verilənləri #1
3
1 10
9 9
10 3
Çıxış verilənləri #1
1
Mənbə Stage III All-Ukrainian School Olympiad 2012-2013, Round 2