Помещенные в карантин для защиты во время вспышки COWVID-19, коровы фермера Джона придумали новый способ облегчить себе скуку: изучать физику на высшем уровне! Фактически, коровы даже сумели открыть новую субатомную частицу, которую они назвали "муу частицей".
Коровы сейчас проводят эксперимент с n муу частицами. Частица 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 (1 ≤ n ≤ 10^5
) - начальное количество частиц муу. Каждая из следующих n строк содержит два целых числа, обозначающих спин одной частицы. У каждой частицы свой спин.
Выведите одно целое число - наименьшее количество частиц муу, которое может остаться после произвольной последовательности взаимодействий.
Одна из возможных последовательностей взаимодействия:
Частицы 1 и 4 взаимодействуют, частица 1 исчезает.
Частицы 2 и 4 взаимодействуют, частица 4 исчезает.
Частицы 2 и 3 взаимодействуют, частица 3 исчезает.Остается только частица 2.
Частица 3 не может взаимодействовать ни с одной из двух других частиц, поэтому она должна оставаться. Также должна остаться хотя бы одна из частиц 1 или 2.