← 返回题目列表

Codeforces · 2211/H

H. 中值缺失

中文机器翻译题面 查看原题

给你一个大小为 $$$n$$$ 的排列 $$$p$$$。您可以多次执行以下操作:

  • 选择大小为 $$$3$$$ 的子数组。然后,删除其中第二小的元素。

例如,对于排列$$$[2,4,5,3,1]$$$,您可以选择子数组$$$[\mathbf{2},\mathbf{4},\mathbf{5},3,1]$$$。由于$$$4$$$是$$$[2,4,5]$$$中第二小的元素,因此可以删除$$$4$$$得到数组$$$[2,5,3,1]$$$。

对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,找到包含数字 $$$p_i$$$ 的可获得数组的最小长度。请注意,这个问题要针对每个 $$$i$$$ 独立解决。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 排列的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$)。

保证给定的 $$$p$$$ 是一个排列。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在新行中输出 $$$n$$$ 数字:$$$i=1,2,\ldots,n$$$ 的答案。

示例

输入
复制

6
1
1
4
4 2 1 3
5
4 1 3 5 2
6
1 4 3 5 2 6
6
1 5 3 4 2 6
8
4 3 7 5 1 6 8 2

输出
复制

1
2 4 2 3
3 2 5 2 3
2 3 3 3 3 2
2 3 5 5 3 2
3 3 3 5 2 5 2 3

注意

在第二个示例中,对于 $$$i=1$$$,我们可以得到一个大小为 $$$2$$$ 的数组,如下所示:

  • 选择子数组$$$[4,2,1]$$$。删除中位数 $$$2$$$。该数组现在是$$$[4,1,3]$$$。
  • 选择子数组$$$[4,1,3]$$$。删除中位数 $$$3$$$。该数组现在是$$$[4,1]$$$。

可以证明$$$2$$$是包含$$$a_1=4$$$的任何可达数组的最小长度。

对于$$$i=4$$$,答案是$$$3$$$,包含$$$a_4=3$$$的最小长度可达数组是$$$[4,1,3]$$$。