Description

很快，新的手机服务提供商 BerLine 将在 Berland 开始运营！

客户服务的启动计划沿着首都的主街进行。已经有 $n$ 个基站安装完毕，它们沿着主街从左到右依次排列，编号从 $1$ 到 $n$。

目前，所有这些基站都处于关闭状态。它们将按照某个排列 $p = [p_1, p_2, \dots, p_n]$（$1 \le p_i \le n$）依次开启，每天开启一个基站，其中 $p_i$ 表示第 $i$ 天开启的基站编号。因此，开启所有基站需要 $n$ 天时间。

每个基站都有一个工作频率 $f_i$ —— 这是一个介于 $1$ 到 $24$ 之间的整数。

对于基站的工作频率有一个重要要求：考虑任意时刻，对于任何手机用户，如果查看其手机信号覆盖范围内所有已开启的基站，那么在这些基站中至少有一个的工作频率在该组基站中是唯一的。由于手机的信号强度和用户位置事先未知，这意味着对于任何非空的已开启基站子段，其中至少有一个基站的工作频率在该子段中是唯一的。

例如，假设 $n = 7$，所有基站都已开启，且其频率为 $f = [1, 2, 1, 3, 1, 2, 1]$。对于任意子段，该子段内都存在一个频率唯一的基站。但如果 $f = [1, 2, 1, 2, 3, 2, 1]$，则子段 $[1, 2, 1, 2]$（从第 $1$ 个到第 $4$ 个基站）中没有频率是唯一的。

你的任务是为每个基站分配一个 $1$ 到 $24$ 之间的频率，使得在任意时刻（按照给定排列 $p$ 开启基站的过程中）都满足上述频率要求。

Input Format

输入的第一行包含一个整数 $t$（$1 \le t \le 50$）—— 测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 8\,500$）—— BerLine 基站的数量。

第二行包含 $n$ 个不同的整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）—— 基站开启的顺序，即第 $i$ 天开启编号为 $p_i$ 的基站。

保证所有测试用例都存在正确的解。

Output Format

对于每个测试用例，输出一行 $n$ 个整数 $f_1, f_2, \dots, f_n$（$1 \le f_i \le 24$）—— 分配给每个基站的工作频率。如果有多个解，输出任意一个即可。

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 3 2
10 20 10
1
2 3 4 5 3 1 3 5 4 2
1 2 3 4 5 6 7 8 9 10

Hint

在第一个测试用例中，$n = 3$，$p = [1, 3, 2]$。可以给基站分配频率 $[1, 3, 2]$。

• 第 1 天：只有基站 $1$ 开启，其频率为 $1$。
• 第 2 天：基站 $1$ 和 $3$ 开启，频率为 $[1, 2]$。
• 第 3 天：所有基站开启，频率为 $[1, 3, 2]$（沿街道方向排列）。

在每一天，任何非空的已开启基站子段中都有一个频率唯一的基站。可以证明，在这个测试用例中必须使用三个不同的频率。

翻译由 DeepSeek V3 完成