P12941 [NERC 2019] Help BerLine

很快，新的手机服务提供商 **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$ 开启基站的过程中）都满足上述频率要求。

输入的第一行包含一个整数 $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$ 的基站。 保证所有测试用例都存在正确的解。

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

在第一个测试用例中，$n = 3$，$p = [1, 3, 2]$。可以给基站分配频率 $[1, 3, 2]$。 - 第 1 天：只有基站 $1$ 开启，其频率为 $1$。 - 第 2 天：基站 $1$ 和 $3$ 开启，频率为 $[1, 2]$。 - 第 3 天：所有基站开启，频率为 $[1, 3, 2]$（沿街道方向排列）。 在每一天，任何非空的已开启基站子段中都有一个频率唯一的基站。可以证明，在这个测试用例中必须使用三个不同的频率。 翻译由 DeepSeek V3 完成