给你一个大小为 $$$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$$$ 的答案。
示例
输入复制
61144 2 1 354 1 3 5 261 4 3 5 2 661 5 3 4 2 684 3 7 5 1 6 8 2
输出复制
12 4 2 33 2 5 2 32 3 3 3 3 22 3 5 5 3 23 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]$$$。