F. Конференция
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вас попросили организовать очень важную конференцию об искусстве. Первый шаг — выбрать даты.

Конференция должна длиться некоторое число подряд идущих дней. Каждый день на конференции должен выступать один лектор, причём один и тот же лектор не может выступать более одного раза.

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

Некоторый отрезок дней можно выбрать в качестве дат конференции в том случае, если существует способ на каждый из дней отрезка назначить доступного в этот день лектора, при этом назначив каждого лектора не более чем на один день.

Для каждого $$$k$$$ от $$$1$$$ до $$$n$$$ найдите, сколько есть способов выбрать отрезок из $$$k$$$ подряд идущих дней в качестве дат конференции.

Входные данные

Первая строка содержит одно целое число $$$n$$$ — число потенциальных лекторов ($$$1 \le n \le 2 \cdot 10^5$$$).

Каждая из следующих $$$n$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ — отрезок доступных дней для $$$i$$$-го лектора ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$).

Выходные данные

Выведите $$$n$$$ целых чисел, где $$$k$$$-е число обозначает число способов выбрать отрезок из $$$k$$$ подряд идущих дней в качестве дат конференции.

Примеры
Входные данные
3
1 2
3 4
5 6
Выходные данные
6
2
0
Входные данные
5
1 3
1 3
1 3
1 3
1 3
Выходные данные
3
2
1
0
0
Примечание

В первом примере конференцию из одного дня можно устроить в любой из дней с $$$1$$$ по $$$6$$$. Конференцию из двух дней можно устроить с дня $$$2$$$ по день $$$3$$$, а также с дня $$$4$$$ по день $$$5$$$.

Во втором примере, несмотря на то, что сразу пятеро лекторов выразили желание выступить на конференции, все они доступны только в дни с $$$1$$$ по $$$3$$$, поэтому устроить конференцию длиннее трёх дней не выйдет.