Задачи
Помогите BerLine
Помогите BerLine
Совсем скоро в Берляндии начнет работу новый оператор сотовой связи "БерЛайн"!
Старт обслуживания клиентов планируется по центральной улице столицы. Уже установлено $n$ базовых станций. Они расположены друг за другом вдоль главной улицы в порядке от $1$-го до $n$-го слева направо.
В настоящее время все эти базовые станции отключены. Они будут включаться по одной, по одной базовой станции в день, по некоторой перестановке $p = [p_1, p_2, ..., p_n]~(1 \le p_i \le n)$, где $p_i$ --- номер базовой станции, которая будет включена в $i$-ый день. Таким образом, для включения всех базовых станций потребуется $n$ дней.
Каждая базовая станция характеризуется своей рабочей частотой $f_i$ --- целым числом от $1$ до $24$ включительно.
Существует важное требование к рабочим частотам базовых станций. Рассмотрим произвольный момент времени. Для любого владельца телефона, если учесть все включенные базовые станции в зоне его доступа, то в этом наборе базовых станций должна быть хотя бы одна, рабочая частота которой является уникальной среди частот этих станций. Так как мощность телефона и его местонахождение не известны заранее, то для любого непустого подотрезка включенных базовых станций хотя бы одна из них должна иметь рабочую частоту, уникальную среди станций этого подсегмента.
Например, рассмотрим случай $n = 7$, все $n$ станций включены, а их частоты равны $f = [1, 2, 1, 3, 1, 2, 1]$. Рассмотрим любой подотрезок базовых станций - в этом подсегменте имеется базовая станция с уникальной частотой. Однако если $f = [1, 2, 1, 2, 3, 2, 1]$, то на отрезке $[1, 2, 1, 2]$ от индекса $1$ до индекса $4$ включительно уникальной частоты нет.
Ваша задача - назначить частоту от $1$ до $24$ каждой из $n$ базовых станций таким образом, чтобы потребность в частоте выполнялась в каждый момент времени. Помните, что базовые станции включаются в порядке заданной перестановки $p$.
\InputFile
Первая строка содержит целое число $t~(1 \le t \le 50)$ --- количество тестов. Далее следуют $t$ тестов.
Первая строка каждого теста содержит целое число $n~(1 \le n \le 8500)$ --- количество базовых станций "БерЛайн".
Следующая строка содержит $n$ различных целых чисел $p_1, p_2, ..., p_n~(1 \le p_i \le n)$ --- порядок включения базовых станций, т.е. в $i$-ый день включается базовая станция с индексом $p_i$.
Гарантируется, что правильный ответ существует для всех входных тестов.
\OutputFile
Выведите ровно $t$ строк, где $j$-я строка содержит ответ для $j$-го теста. Выведите требуемые частоты $f_1, f_2, ..., f_n~(1 \le f_i \le 24)$. Если возможных ответов несколько, выведите любой из них.
\Examples
В первом тесте $n = 3$ и $p = [1, 3, 2]$. Базовым станциям могут быть назначены частоты $[1, 3, 2]$.
\begin{itemize}
\item День $1$: включена только базовая станция $1$, ее частота $1$.
\item День $2$: включены базовые станции $1$ и $3$, их частоты $[1, 2]$.
\item День $3$: все базовые станции включены, их частоты $[1, 3, 2]$ (вдоль улицы).
\end{itemize}
Каждый день в каждом непустом подотрезке включенных базовых станций находится базовая станция с уникальной частотой. Можно показать, что в этом тесте необходимы три различные частоты.
Входные данные #1
5 3 1 3 2 3 1 2 3 1 1 10 6 10 4 2 7 9 5 8 3 1 10 2 4 6 9 1 8 10 5 3 7
Выходные данные #1
1 3 2 1 2 1 1 1 5 2 1 2 4 6 2 1 5 1 4 1 5 2 1 3 2 4 6