H. Удаление медианы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$p$$$ размера $$$n$$$. Вы можете выполнить следующую операцию любое количество раз:

  • Выбрать подмассив размера $$$3$$$. Затем удалить второй по величине минимальный элемент в нём.

Например, для перестановки $$$[2,4,5,3,1]$$$ можно выбрать подмассив $$$[\mathbf{2},\mathbf{4},\mathbf{5},3,1]$$$. Так как $$$4$$$ является вторым по величине минимальным элементом среди $$$[2,4,5]$$$, вы можете удалить $$$4$$$ и получить массив $$$[2,5,3,1]$$$.

Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ найдите минимальную длину массива, который можно получить и который содержит число $$$p_i$$$. Обратите внимание, что эту задачу нужно решать независимо для каждого $$$i$$$.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$).

Гарантируется, что данный массив $$$p$$$ является перестановкой.

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

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

Для каждого набора входных данных выведите на отдельной строке $$$n$$$ чисел: ответ для $$$i=1,2,\ldots,n$$$.

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

Во втором примере для $$$i=1$$$ мы можем получить массив размера $$$2$$$ следующим образом:

  • Выбрать подмассив $$$[4,2,1]$$$. Удалить медиану $$$2$$$. Теперь массив равен $$$[4,1,3]$$$.
  • Выбрать подмассив $$$[4,1,3]$$$. Удалить медиану $$$3$$$. Теперь массив равен $$$[4,1]$$$.

Можно показать, что $$$2$$$ — это минимальная длина любого достижимого массива, содержащего $$$a_1=4$$$.

Для $$$i=4$$$ ответ равен $$$3$$$, при этом массив минимальной достижимой длины, содержащий $$$a_4=3$$$, равен $$$[4,1,3]$$$.