29541번 - Маршрутное такси 스페셜 저지다국어

Жители Флатландии обычно передвигаются по городу на таком виде общественного транспорта, как маршрутное такси --- он быстрый, удобный и относительно недорогой.

К сожалению, есть одна проблема --- производители автобусов для маршрутных такси спроектировали их так, что пассажиры испытывают большие неудобства, пробираясь друг мимо друга к свободным местам в автобусе.

Спиридон --- водитель маршрутного такси, который уже давно работает на своем маршруте и знает всех пассажиров, проезжающих на его автобусе изо дня в день. Поэтому, он решил спланировать рассадку пассажиров таким образом, чтобы минимизировать количество прохождений пассажиров друг мимо друга.

Про каждого пассажира известно, когда он входит и выходит из автобуса. Все места расположены в ряд и пронумерованы от 1 до $n$, начиная от ближайшего места ко входу. Таким образом получается, что когда пассажир, сидящий на $i$-ом месте входит или выходит, он проходит мимо всех пассажиров, сидящих на местах с номерами меньше $i$.

Во время поездки пассажиры не перемещаются по автобусу, то есть занимают одно и то же место все время.

Первая строка входного файла содержит $n$ ($1 \le n \le 100000$) --- количество пассажиров автобуса.

Следующие $n$ строк содержат по паре чисел $a_i, b_i$ ($1 \le a_i < b_i \le 2n$)--- номера остановок, на которых входят входит и выходит $i$-ый пассажир.

На каждой остановке входит или выходит не более одного человека.

В первую строку входного файла выведите одно число --- минимальное количество прохождений людей друг мимо друга.

Во вторую строку выведите $n$ чисел, $i$-ое из которых --- номер места, на которое должен сесть $i$-ый пассажир.