很快,新的手机服务提供商“BerLine”将在 Berland 开始运营!
计划沿首都主要街道开始提供客户服务。已安装 $$$n$$$ 基站。它们按照从左到右从 $$$1$$$-st 到 $$$n$$$-th 的顺序依次分布在主街道上。
目前,所有这些基站均已关闭。它们将根据某种排列逐个打开,每天一个基站 $$$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$$$ 到索引 $$$4$$$(包含这两个端点)的段 $$$[1, 2, 1, 2]$$$ 上不存在唯一频率。
您的任务是为每个 $$$n$$$ 基站分配从 $$$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。 e.在第 $$$i$$$ 天,索引为 $$$p_i$$$ 的基站开启。
保证输入中的所有测试用例都存在正确答案。
输出
准确打印 $$$t$$$ 行,其中第 $$$j$$$ 行包含输入中第 $$$j$$$ 测试用例的答案。打印所需的频率 $$$f_1, f_2, \dots, f_n$$$ ($$$1 \le f_i \le 24$$$)。如果有多个可能的答案,请打印其中任何一个。
示例
输入 #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 10 20 10 1 2 3 4 5 3 1 3 5 4 2 1 2 3 4 5 6 7 8 9 10
注意
在第一个测试用例中 $$$n = 3$$$ 和 $$$p = [1, 3, 2]$$$。可以为基站分配频率$$$[1,3,2]$$$。
- 第 1 天:仅打开基站 $$$1$$$,其频率为 $$$1$$$。
- 第 2 天:基站 $$$1$$$ 和 $$$3$$$ 开启,频率为 $$$[1, 2]$$$。
- 第 3 天:所有基站均开启,频率为 $$$[1, 3, 2]$$$(沿街道方向)。
每天,打开的基站的每个非空子段在该子段中都有一个具有唯一频率的基站。可以看出,在此测试案例中需要三个不同的频率。