Муу частицы
Муу частицы
Помещенные в карантин для защиты во время вспышки COWVID-19, коровы фермера Джона придумали новый способ облегчить себе скуку: изучать физику на высшем уровне! Фактически, коровы даже сумели открыть новую субатомную частицу, которую они назвали "муу частицей".
Коровы сейчас проводят эксперимент с n муу частицами. Частица i имеет "спин", описываемый двумя целыми числами xi
и yi
в диапазоне -109
... 109
включительно. Иногда взаимодействуют две муу частицы. Это может произойти с частицами со спинами (xi
, yi
) и (xj
, yj
), только если xi
≤ xj
иyi
≤ yj
. В этих условиях возможно, что ровно одна из этих двух частиц может исчезнуть (и с другой частицей ничего не произойдет). В любой момент времени произойдет не более одного взаимодействия.
Коровы хотят знать минимальное количество частиц муу, которое может остаться после произвольной последовательности взаимодействий.
Входные данные
Первая строка содержит единственное целое число n (1 ≤ n ≤ 105
) - начальное количество частиц муу. Каждая из следующих n строк содержит два целых числа, обозначающих спин одной частицы. У каждой частицы свой спин.
Выходные данные
Выведите одно целое число - наименьшее количество частиц муу, которое может остаться после произвольной последовательности взаимодействий.
Пример 1
Одна из возможных последовательностей взаимодействия:
- Частицы 1 и 4 взаимодействуют, частица 1 исчезает.
- Частицы 2 и 4 взаимодействуют, частица 4 исчезает.
- Частицы 2 и 3 взаимодействуют, частица 3 исчезает. Остается только частица 2.
Пример 2
Частица 3 не может взаимодействовать ни с одной из двух других частиц, поэтому она должна оставаться. Также должна остаться хотя бы одна из частиц 1 или 2.
4 1 0 0 1 -1 0 0 -1
1
3 0 0 1 1 -1 3
2