CF2103D.Local Construction

在数组 $b_1, b_2, \ldots, b_m$ 中，元素 $b_i$（$1 \le i \le m$）是局部最小值当且仅当满足以下至少一个条件：

• $2 \le i \le m - 1$ 且 $b_i < b_{i - 1}$ 且 $b_i < b_{i + 1}$，或
• $i = 1$ 且 $b_1 < b_2$，或
• $i = m$ 且 $b_m < b_{m - 1}$。

类似地，元素 $b_i$（$1 \le i \le m$）是局部最大值当且仅当满足以下至少一个条件：

• $2 \le i \le m - 1$ 且 $b_i > b_{i - 1}$ 且 $b_i > b_{i + 1}$，或
• $i = 1$ 且 $b_1 > b_2$，或
• $i = m$ 且 $b_m > b_{m - 1}$。

注意，对于只有一个元素的数组，局部最小值和局部最大值没有定义。

给定一个隐藏的排列 $^{\text{∗}}$ $p$，其长度为 $n$。对该排列交替执行以下两种操作，从操作 1 开始，直到 $p$ 中只剩一个元素：

• 操作 1 —— 删除 $p$ 中所有不是局部最小值的元素。
• 操作 2 —— 删除 $p$ 中所有不是局部最大值的元素。

具体来说，在每次奇数轮迭代时执行操作 1，在每次偶数轮迭代时执行操作 2，直到 $p$ 中只剩一个元素。

对于每个下标 $i$（$1 \le i \le n$），设 $a_i$ 为元素 $p_i$ 被删除的轮次编号，若未被删除则设为 $-1$。

可以证明，最多经过 $\lceil \log_2 n \rceil$ 轮迭代后 $p$ 中只剩一个元素（即 $a_i \le \lceil \log_2 n \rceil$）。

给定数组 $a_1, a_2, \ldots, a_n$，你的任务是构造任意一个满足数组 $a$ 的排列 $p$。

$^{\text{∗}}$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 的 $n$ 个不同整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（因为 $2$ 出现了两次），$[1,3,4]$ 也不是（因为 $n=3$ 但出现了 $4$）。

每个测试包含多个测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。

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

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le \lceil \log_2 n \rceil$ 或 $a_i = -1$）——元素 $p_i$ 被删除的轮次编号。

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

保证至少存在一个满足数组 $a$ 的排列 $p$。

对于每个测试用例，输出 $n$ 个整数，表示满足数组 $a$ 的排列。

如果有多个解，输出任意一个即可。

在第一个测试用例中，对排列 $[3, 2, 1]$ 执行的操作如下：

1. $[3, 2, 1]$ 的唯一局部最小值是 $1$，因此删除 $3$ 和 $2$。此时只剩一个元素，过程终止。
   这满足数组 $a = [1, 1, -1]$，因为 $p_1$ 和 $p_2$ 在第 1 轮被删除，而 $p_3$ 未被删除。

在第二个测试用例中，对排列 $[4, 3, 5, 1, 2]$ 执行的操作如下：

1. $[4, 3, 5, 1, 2]$ 的局部最小值是 $3$ 和 $1$，因此删除 $4$、$5$ 和 $2$。
2. $[3, 1]$ 的唯一局部最大值是 $3$，因此删除 $1$。此时只剩一个元素，过程终止。
   这满足数组 $a = [1, -1, 1, 2, 1]$，因为 $p_1$、$p_3$ 和 $p_5$ 在第 1 轮被删除，$p_4$ 在第 2 轮被删除，$p_2$ 未被删除。

在第三个测试用例中，对排列 $[6, 7, 2, 4, 3, 8, 5, 1]$ 执行的操作如下：

1. 局部最小值是 $6$、$2$、$3$ 和 $1$，因此删除 $7$、$4$、$8$ 和 $5$。
2. 局部最大值是 $6$ 和 $3$，因此删除 $2$ 和 $1$。
3. 局部最小值是 $3$，因此删除 $6$。此时只剩一个元素，过程终止。

在第四个测试用例中，一个满足条件的排列是 $[6, 5, 2, 1, 3, 4, 7]$。$1$ 是唯一的局部最小值，因此它会在第一轮后保留。注意，其他排列也可能满足条件，例如 $[6, 4, 3, 1, 2, 5, 7]$ 也是正确的解。

翻译由 DeepSeek V3 完成