给你一个大小为 $$$n$$$ 的排列$$$^{\text{∗}}$$$ $$$p$$$。您可以多次执行以下操作:
- 选择一个大小为 $$$3$$$ 的子数组$$$^{\text{†}}$$$。然后,删除其中最小或最大的元素。
例如,对于排列$$$[2,4,5,3,1]$$$,您可以选择子数组$$$[\mathbf{2},\mathbf{4},\mathbf{5},3,1]$$$。由于 $$$5=\operatorname{max}(2,4,5)$$$。删除$$$5$$$即可得到数组$$$[2,4,3,1]$$$。您也可以选择删除 $$$2$$$,而不是 $$$2=\operatorname{min}(2,4,5)$$$。
对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,找到包含数字 $$$p_i$$$ 的可获得数组的最小长度。请注意,这个问题要针对每个 $$$i$$$ 独立解决。
$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
$$$^{\text{†}}$$$数组 $$$a$$$ 是数组 $$$b$$$ 的子数组,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 数组的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$)。保证从 $$$1$$$ 到 $$$n$$$ 的每个元素恰好出现一次。
输出
对于每个测试用例,在新行中输出 $$$n$$$ 数字:$$$i=1,2,\ldots,n$$$ 的答案。
示例
输入复制
21132 1 3
输出复制
12 2 2
注意
在第一个示例中,我们无法执行任何操作,因为数组的大小只有 $$$1 \lt 3$$$。
在第二个例子中,对于$$$i=2$$$,我们可以选择子数组$$$[2,1,3]$$$,删除最大的数$$$3$$$得到数组$$$[2,1]$$$。可以证明$$$2$$$是包含$$$a_2=1$$$的任何可达数组的最小长度。