Ця задача ідентична попередній задачі «Шеф приймає відвідувачів (2)» як за загальною фабулою, так і за точним питанням та форматом вхідних даних і результату; відмінність лише в обмеженні на максимальне ~N~ (~10^5~, а не ~10^4~).

Шеф завжди приділяє всім відвідувачам рівні проміжки часу (наприклад, кожному по п'ять хвилин); щоб потрапити на прийом, слід напередодні записатися у секретарки.

При реєстрації відвідувач вказує єдиний інтервал часу, що задається парою ~[A_i; B_i]~ (початковий та кінцевий моменти, коли він згоден заходити на прийом). ~A_i~ і ~B_i~ – невід'ємні цілі числа, що означають кількість інтервалів прийому, що пройшли з початку робочого дня Шефа (отже, момент початку робочого часу Шефа має номер 0). Допоможіть секретарці обробляти зібрані записи і складати графік прийому.

Вхідні дані

Перший рядок містить кількість відвідувачів (~2\leqslant N\leqslant 10^5~), далі йдуть ще ~N~ рядків, у кожному з яких по два числа ~А_i~ і ~B_i~, ~0\leqslant A_i\leqslant B_i\leqslant 2N~.

Результати

Програма повинна вивести на екран 1 (якщо встановити графік прийому можливо), або 0 (якщо неможливо). Якщо відповідь позитивна (1), то далі в тому ж рядку через пропуски програма має вивести послідовність чисел-номерів відвідувачів у порядку, як вони потрапляють на прийом. Якщо потрібно, щоб у якийсь момент ніхто не заходив на прийом, слід виводити ~–1~. Якщо існують різні графіки, що цілком задовольняють вхідним даним, слід вивести будь-який один з них.

Приклади

Вхід

3
1 2
0 1
2 2

Результат

1 2 1 3

Вхід

3
1 2
1 2
1 2

Результат

0

Вхід

3
1 2
1 2
2 4

Результат

1 -1 1 2 3

Примітки

Зверніть увагу, що ~B_i~ є останнім моментом, коли відвідувач усе ще згоден заходити на прийом (і в першому, і в третьому прикладах лише завдяки цьому і вдається побудувати порядок прийому).

Зверніть увагу, що справді бувають ситуації, коли графік можна побудувати лише таким, коли в деякі моменти часу ніхто не заходить на прийом.