CF1267H 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$，所有 $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$ 之间的频率，使得在每一时刻都满足上述频率要求。请注意，基站的开启顺序由给定的排列 $p$ 决定。

输入的第一行包含一个整数 $t$（$1 \le t \le 50$），表示测试用例的数量。接下来是 $t$ 个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 8500$），表示“BerLine”基站的数量。 接下来的第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$），表示基站的开启顺序，即第 $i$ 天开启编号为 $p_i$ 的基站。 保证所有测试用例都存在合法解。

输出恰好 $t$ 行，第 $j$ 行为第 $j$ 个测试用例的答案。请输出满足要求的频率 $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$ 和 $3$，它们的频率为 $[1,2]$。 - 第三天：所有基站都已开启，频率为 $[1,3,2]$（沿街道方向）。 每一天，任意非空的已开启基站连续子区间都存在一个基站在该区间内拥有唯一的频率。可以证明本例需要三种不同的频率。 由 ChatGPT 4.1 翻译