eolymp
Задачи

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

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

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

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

Входные данные

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

Выходные данные

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

Лимит времени 0.75 секунд
Лимит использования памяти 128 MiB
Входные данные #1
3
1 10
9 9
10 3
Выходные данные #1
1
Источник III этап Всеукраинской олимпиады школьников 2012-2013, 2 тур