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

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

  • Выбрать подмассив$$$^{\text{†}}$$$ размера $$$3$$$. Затем удалить из него либо наименьший, либо наибольший элемент.

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

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

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

$$$^{\text{†}}$$$Массив $$$a$$$ является подмассивом массива $$$b$$$, если $$$a$$$ может быть получен из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — длину массива.

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

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

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

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

В первом наборе входных данных мы не можем выполнить ни одной операции, так как размер массива равен всего $$$1 \lt 3$$$.

Во втором наборе входных данных для $$$i=2$$$ мы можем выбрать подмассив $$$[2,1,3]$$$ и удалить наибольшее число $$$3$$$, получив массив $$$[2,1]$$$. Можно показать, что $$$2$$$ — минимальная длина любого достижимого массива, содержащего $$$a_2=1$$$.