CF2211H Median Deletion

给定一个大小为 $n$ 的排列 $p$。你可以执行以下操作任意多次： - 选择一个长度为 $3$ 的连续子数组，然后删除其中第二小的元素。 例如，对于排列 $2,4,5,3,1$，可以选择连续子数组 $[2,4,5]$，其中第二小的元素是 $4$，删除后得到 $[2,5,3,1]$。 对于每个 $1\le i\le n$，求最终得到的数组包含 $p_i$ 时，该数组的最小长度。每个 $i$ 的问题是独立的。

每个测试点包含多组数据。第一行一个正整数 $t$（$1 \le t \le 10^4$）表示数据组数。 对于每组数据，第一行一个整数 $n$（$1 \le n \le 2 \times 10^5$），第二行 $n$ 个整数表示排列 $p$。 单个测试点所有数据的 $n$ 之和不超过 $2 \times 10^5$。

共 $t$ 行，对于每组数据，输出一行 $n$ 个整数，分别表示 $i = 1,2,\ldots,n$ 的答案。

对于样例的第二组数据的 $i=1$，可以通过以下操作得到长度为 $2$ 的数组： - 选择子数组 $[4,2,1]$，删除中位数 2，得到 $[4,1,3]$。 - 选择子数组 $[4,1,3]$，删除中位数 3，得到 $[4,1]$。 可以证明这是最优解。 对于 $i = 4$，答案是 3，可得到的包含 $p_4 = 3$ 的最短数组是 $[4,1,3]$。