H. Ice Baby
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Наибольшая неубывающая подпоследовательность массива целых чисел $$$a_1, a_2, \ldots, a_n$$$ — это самая длинная последовательность индексов $$$1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq n$$$, такая что $$$a_{i_1} \leq a_{i_2} \leq \ldots \leq a_{i_k}$$$. Длина последовательности определяется как количество элементов последовательности. Например, длина наибольшей неубывающей подпоследовательности массива $$$a = [3, 1, 4, 1, 2]$$$ равна $$$3$$$.

Вам даны два массива целых чисел $$$l_1, l_2, \ldots, l_n$$$ и $$$r_1, r_2, \ldots, r_n$$$. Для каждого $$$1 \le k \le n$$$ решите следующую задачу:

  • Рассмотрим все массивы целых чисел $$$a$$$ длины $$$k$$$, такие что для каждого $$$1 \leq i \leq k$$$ верно, что $$$l_i \leq a_i \leq r_i$$$. Найдите максимальную длину наибольшей неубывающей подпоследовательности среди всех таких массивов.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длина массивов $$$l$$$ и $$$r$$$.

Следующие $$$n$$$ строк каждого набора входных данных содержат два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
6
1
1 1
2
3 4
1 2
4
4 5
3 4
1 3
3 3
8
6 8
4 6
3 5
5 5
3 4
1 3
2 4
3 3
5
1 2
6 8
4 5
2 3
3 3
11
35 120
66 229
41 266
98 164
55 153
125 174
139 237
30 72
138 212
109 123
174 196
Выходные данные
1 
1 1 
1 2 2 3 
1 2 2 3 3 3 4 5 
1 2 2 2 3 
1 2 3 4 5 6 7 7 8 8 9
Примечание

В первом наборе входных данных возможен только массив $$$a = [1]$$$. У этого массива длина наибольшей неубывающей подпоследовательности равна $$$1$$$.

Во втором наборе входных данных для $$$k = 2$$$ как бы мы ни выбирали значения $$$a_1$$$ и $$$a_2$$$, всегда будет выполняться условие, что $$$a_1 \gt a_2$$$. Поэтому ответ для $$$k = 2$$$ будет равен $$$1$$$.

В третьем наборе входных данных для $$$k = 4$$$ можно выбрать массив $$$a = [5, 3, 3, 3]$$$. Длина наибольшей неубывающей подпоследовательности у этого массива равна $$$3$$$.

В четвертом наборе входных данных для $$$k = 8$$$ можно выбрать массив $$$a = [7, 5, 3, 5, 3, 3, 3, 3]$$$. Длина наибольшей неубывающей подпоследовательности у этого массива равна $$$5$$$.

В пятом наборе входных данных для $$$k = 5$$$ можно выбрать массив $$$a = [2, 8, 5, 3, 3]$$$. Длина наибольшей неубывающей подпоследовательности у этого массива равна $$$3$$$.