Задача
Углубившись на карантине в изучение физики, коровы открыли "му-частицы"
В настоящий момент они проводят эксперимент с N "му-частицами" (1 ≤N ≤ 10
5). Частица i имеет "спин", описываемый двумя целыми числами x
i и y
i в диапазоне −10
9…10
9 включительно. Иногда две "му-частицы" взаимодействуют. Это может случиться только с такими частицами со спинами (x
i,y
i) и (x
j,y
j) у которых x
i≤x
j и y
i≤y
j. При этих условиях ровно одна из этих частиц исчезает (а с другой ничего не случится). В каждый момент времени может случиться не более одного взаимодействия.
Коровы хотят узнать минимальное количество "му-частиц", которые могут остаться после некоторой произвольной последовательности взаимодействий.
Входные данные
Первая строка содержит одно целое число N, начальное число "му-частиц". Каждая из последующих N строк содержит два разделённых пробелом целых числа, определяющих спин этой частицы. Все спины различны.
Выходные данные
Одно целое число, минимальное количество "му-частиц", которые могут остаться после некоторой произвольной последовательности взаимодействий.
Примеры
| № |
Входные данные |
Выходные данные |
Примечание |
| 1 |
4
1 0
0 1
-1 0
0 -1 |
1 |
Одна из возможных последовательностей взаимодействий:
Частицы 1 и 4 взаимодействуют, частица 1 исчезает.
Частицы 2 и 4 взаимодействуют, частица 4 исчезает.
Частицы 2 и 3 взаимодействуют, частица 3 исчезает.
Только частица 2 остаётся. |
| 2 |
3
0 0
1 1
-1 3 |
2 |
Частица 3 не может взаимодействовать ни с одной из других частиц, поэтому она должна остаться. Одна из частиц 1 и 2 тоже должна остаться. |