Допоможіть BerLine#9587

Допоможіть BerLine

2 секунди

128 мегабайтів

Дуже складна

Зовсім скоро в Берляндії розпочне роботу новий оператор мобільного зв'язку "БерЛайн"!

Старт обслуговування клієнтів планується по центральній вулиці столиці. Вже встановлено $n$ базових станцій. Вони розташовані одна за одною вздовж головної вулиці в порядку від $1$ -го до $n$ -го зліва направо.

Наразі всі ці базові станції вимкнені. Вони будуть вмикатися по одній, по одній базовій станції на день, за певною перестановкою $p = [p_{1}, p_{2}, ..., p_{n}] (1 \leq p_{i} \leq n)$ p = [p_1, p_2, ..., p_n]~(1 \le p_i \le n), де $p_{i}$ p_i — номер базової станції, яка буде включена в $i$ -ий день. Таким чином, для включення всіх базових станцій знадобиться $n$ днів.

Кожна базова станція характеризується своєю робочою частотою $f_{i}$ f_i — цілим числом від $1$ до $24$ включно.

Існує важлива вимога до робочих частот базових станцій. Розглянемо довільний момент часу. Для будь-якого власника телефону, якщо врахувати всі включені базові станції в зоні його доступу, то в цьому наборі базових станцій повинна бути хоча б одна, робоча частота якої є унікальною серед частот цих станцій. Оскільки потужність телефону і його місцезнаходження не відомі заздалегідь, то для будь-якого непустого підсегмента включених базових станцій хоча б одна з них повинна мати робочу частоту, унікальну серед станцій цього підсегмента.

Наприклад, розглянемо випадок $n = 7$ n = 7, всі $n$ станцій включені, а їх частоти дорівнюють $f = [1, 2, 1, 3, 1, 2, 1]$ f = [1, 2, 1, 3, 1, 2, 1]. Розглянемо будь-який підсегмент базових станцій - в цьому підсегменті є базова станція з унікальною частотою. Однак якщо $f = [1, 2, 1, 2, 3, 2, 1]$ f = [1, 2, 1, 2, 3, 2, 1], то на відрізку $[1, 2, 1, 2]$ [1, 2, 1, 2] від індексу $1$ до індексу $4$ включно унікальної частоти немає.

Ваше завдання - призначити частоту від $1$ до $24$ кожній з $n$ базових станцій таким чином, щоб потреба в частоті виконувалася в кожний момент часу. Пам'ятайте, що базові станції вмикаються в порядку заданої перестановки $p$ .

Вхідні дані

Перший рядок містить ціле число $t (1 \leq t \leq 50)$ t~(1 \le t \le 50) — кількість тестів. Далі йдуть $t$ тестів.

Перший рядок кожного тесту містить ціле число $n (1 \leq n \leq 8500)$ n~(1 \le n \le 8500) — кількість базових станцій "БерЛайн".

Наступний рядок містить $n$ різних цілих чисел $p_{1}, p_{2}, ..., p_{n} (1 \leq p_{i} \leq n)$ p_1, p_2, ..., p_n~(1 \le p_i \le n) — порядок включення базових станцій, тобто в $i$ -ий день включається базова станція з індексом $p_{i}$ p_i.

Гарантується, що правильна відповідь існує для всіх вхідних тестів.

Вихідні дані

Виведіть рівно $t$ рядків, де $j$ -й рядок містить відповідь для $j$ -го тесту. Виведіть потрібні частоти $f_{1}, f_{2}, ..., f_{n} (1 \leq f_{i} \leq 24)$ f_1, f_2, ..., f_n~(1 \le f_i \le 24). Якщо можливих відповідей декілька, виведіть будь-яку з них.

Приклади

У першому тесті $n = 3$ n = 3 і $p = [1, 3, 2]$ p = [1, 3, 2]. Базовим станціям можуть бути призначені частоти $[1, 3, 2]$ [1, 3, 2].

День $1$ : включена тільки базова станція $1$ , її частота $1$ .
День $2$ : включені базові станції $1$ і $3$ , їх частоти $[1, 2]$ .
День $3$ : всі базові станції включені, їх частоти $[1, 3, 2]$ [1, 3, 2] (вздовж вулиці).

Кожен день у кожному непустому підсегменті включених базових станцій знаходиться базова станція з унікальною частотою. Можна показати, що в цьому тесті необхідні три різні частоти.

Приклад 1