Вам дана перестановка $$$p$$$ размера $$$n$$$. Вы можете выполнить следующую операцию любое количество раз:
Например, для перестановки $$$[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$$$.
61144 2 1 354 1 3 5 261 4 3 5 2 661 5 3 4 2 684 3 7 5 1 6 8 2
12 4 2 33 2 5 2 32 3 3 3 3 22 3 5 5 3 23 3 3 5 2 5 2 3
Во втором примере для $$$i=1$$$ мы можем получить массив размера $$$2$$$ следующим образом:
Можно показать, что $$$2$$$ — это минимальная длина любого достижимого массива, содержащего $$$a_1=4$$$.
Для $$$i=4$$$ ответ равен $$$3$$$, при этом массив минимальной достижимой длины, содержащий $$$a_4=3$$$, равен $$$[4,1,3]$$$.
