Видалення магічних плиток
Аймок — чарівник.
Його щоденне завдання — розташовувати магічні плитки в рядок, а потім читати магічне заклинання.
Магічні плитки та їх розташування підкоряються наступним правилам:
Кожна магічна плитка має форму трапеції з висотою 1.
Деякі магічні плитки можуть перекриватися з іншими магічними плитками.
Магічні плитки розташовані на 2D координатній системі.
Верхній край магічних плиток лежить на горизонтальному рядку, де його координата y дорівнює 1.
Нижній край магічних плиток лежить на горизонтальному рядку, де його координата y дорівнює 0.
Після завершення читання магічного заклинання він повинен прибрати ці магічні плитки. Одного дня він зрозумів, що прибирання великої кількості магічних плиток є втомливим, тому вирішив спростити цей процес.
Тепер він навчився "Заклинанню Магнетизації", щоб ефективно прибирати магічні плитки. Заклинання прибирає набір магічних плиток одночасно. Будь-яка пара двох магічних плиток у наборі повинна перекриватися одна з одною.
Наприклад, на Рис. 1, він може прочитати Заклинання Магнетизації на всі три магічні плитки, щоб прибрати їх одночасно, оскільки вони всі перекриваються одна з одною. (Зверніть увагу, що висоти магічних плиток навмисно змінені для полегшення розуміння.)
Рис. 1: Набір магічних плиток, які можна прибрати одночасно
Однак, на Рис. 2, він не може прочитати Заклинання Магнетизації на всі три магічні плитки одночасно, оскільки плитка 1 і плитка 3 не перекриваються.
Рис. 2: Набір магічних плиток, які НЕ можна прибрати одночасно
Він хоче прибрати всі магічні плитки з мінімальною кількістю Заклинань Магнетизації, оскільки читання заклинання вимагає значних витрат магічної сили.
Розглянемо випадок на Рис. 3. Він може прибрати всі магічні плитки, прочитавши Заклинання Магнетизації три рази; перше заклинання для плиток 1 і 2, друге заклинання для плиток 3 і 4, і третє заклинання для плиток 5 і 6.
Рис. 3: Один зі способів прибрати всі магічні плитки (НЕ мінімальна кількість заклинань)
Насправді, він може прибрати всі магічні плитки, прочитавши Заклинання Магнетизації лише двічі; перше заклинання для плиток 1, 2 і 3, друге заклинання для плиток 4, 5 і 6. І це мінімальна кількість необхідних заклинань для прибирання всіх магічних плиток.
Рис. 4: Оптимальний спосіб прибрати всі магічні плитки (мінімальна кількість заклинань)
Дано набір магічних плиток, ваше завдання — створити програму, яка виведе мінімальну кількість Заклинань Магнетизації, необхідних для прибирання всіх цих магічних плиток.
Може бути магічна плитка, яка не перекривається з іншими плитками, однак, він все одно повинен прочитати Заклинання Магнетизації, щоб прибрати її.
Вхідні дані
Вхідні дані мають наступний формат:
N
xLower_11 xLower_12 xUpper_11 xUpper_12
xLower_21 xLower_22 xUpper_21 xUpper_22
xLower_31 xLower_32 xUpper_31 xUpper_32
...
xLower_N1 xLower_N2 xUpper_N1 xUpper_N2
Перший рядок містить ціле число N, яке означає кількість магічних плиток.
Потім слідують N рядків, які містять інформацію про магічні плитки.
(i+1)-й рядок включає чотири цілі числа xLower_i1, xLower_i2, xUpper_i1 і xUpper_i2, що означає, що кутові точки i-ї магічної плитки розташовані в точках (xLower_i1, 0), (xLower_i2, 0), (xUpper_i1, 1), (xUpper_i2, 1).
Ви можете припустити, що жодні дві магічні плитки не будуть мати спільні кутові точки. Тобто, всі xLowerij є унікальними, і всі xUpperij також є унікальними. Вхідні дані підкоряються наступним обмеженням:
1 ≤ N ≤ 10^5
1 ≤ xLower_i1 < xLower_i2 ≤ 10^9
1 ≤ xUpper_i1 < xUpper_i2 ≤ 10^9
Всі xLower_ij є унікальними.
Всі xUpper_ij є унікальними.
Вихідні дані
Ваша програма повинна вивести необхідну мінімальну кількість Заклинань Магнетизації для прибирання всіх магічних плиток.