Реклама. Имя входного файла: g.in

Имя входного файла: g.in

Имя выходного файла: g.out

Максимальное время работы на одном тесте: 5 секунд

Максимальный объем используемой памяти: 4 мегабайта

В супермаркете решили время от времени транслировать рекламу новых товаров. Для того, чтобы составить оптимальное расписание трансляции рекламы, руководство супермаркета провело следующее исследование: в течение дня для каждого покупателя, посетившего супермаркет, было зафиксировано время, когда он пришел в супермаркет, и когда он из него ушел.

Менеджер по рекламе предположил, что такое расписание прихода-ухода покупателей сохранится и в последующие дни. Он хочет составить расписание трансляции рекламных роликов, чтобы каждый покупатель услышал не меньше двух рекламных объявлений. В то же время он выдвинул условие, чтобы два рекламных объявления не транслировались одновременно и, поскольку продавцам все время приходится выслушивать эту рекламу, общее число рекламных объявлений за день было минимальным.

Напишите программу, которая составит такое расписание трансляции рекламных роликов. Рекламные объявления можно начинать транслировать только в целые моменты времени. Считается, что каждое рекламное объявление заканчивается до наступления следующего целого момента времени. Если рекламное объявление транслируется в тот момент времени, когда покупатель входит в супермаркет или уходит из него, покупатель это объявление услышать успевает.

Формат входных данных

Во входном файле записано сначала число N — количество покупателей, посетивших супермаркет за день(1≤N≤3000). Затем идет N пар натуральных чисел Ai, Bi, задающих соответственно время прихода и время ухода покупателей из супермаркета (0<Ai<Bi<10⁶).