如果至少满足以下条件之一,则数组 $$$b_1, b_2, \ldots, b_m$$$ 中的元素 $$$b_i$$$ ($$$1\le i\le m$$$) 是局部最小值:
- $$$2\le i\le m - 1$$$ 和 $$$b_i \lt b_{i - 1}$$$ 和 $$$b_i \lt b_{i + 1}$$$,或者
- $$$i = 1$$$ 和 $$$b_1 \lt b_2$$$,或
- $$$i = m$$$ 和 $$$b_m \lt b_{m - 1}$$$。
类似地,数组 $$$b_1, b_2, \ldots, b_m$$$ 中的元素 $$$b_i$$$ ($$$1\le i\le m$$$) 是局部最大值,如果至少满足以下条件之一:
- $$$2\le i\le m - 1$$$ 和 $$$b_i \gt b_{i - 1}$$$ 和 $$$b_i \gt b_{i + 1}$$$,或者
- $$$i = 1$$$ 且 $$$b_1 \gt b_2$$$,或
- $$$i = m$$$ 和 $$$b_m \gt b_{m - 1}$$$。
请注意,对于只有一个元素的数组,没有定义局部最小值和最大值。
有一个隐藏的排列$$$^{\text{*}}$$$ $$$p$$$,长度为$$$n$$$。以下两个操作交替应用于排列 $$$p$$$,从操作 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$$$ 的 $$$n$$$ 元素的任意排列 $$$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$$$ 的排列元素。
如果有多个解,则可以输出其中任何一个。
示例
输入复制
731 1 -151 -1 1 2 183 1 2 1 -1 1 1 271 1 1 -1 1 1 151 1 1 1 -15-1 1 1 1 15-1 1 2 1 2
输出复制
3 2 1 4 3 5 1 2 6 7 2 4 3 8 5 1 6 5 2 1 3 4 7 5 4 3 2 1 1 2 3 4 5 4 5 2 3 1
注意
在第一个测试用例中,运算将应用于排列 $$$[3, 2, 1]$$$,如下所示:
- $$$[3, 2, 1]$$$ 中唯一的局部最小值是 $$$1$$$。因此,元素 $$$3$$$ 和 $$$2$$$ 被删除。只剩下一个元素;因此该过程终止。
这满足数组 $$$a = [1, 1, -1]$$$,因为 $$$p_1$$$ 和 $$$p_2$$$ 都在迭代编号 $$$1$$$ 上被删除,而 $$$p_3$$$ 未被删除。
在第二个测试用例中,运算将应用于排列 $$$p = [4, 3, 5, 1, 2]$$$,如下所示:
- $$$[4, 3, 5, 1, 2]$$$ 中的局部最小值为 $$$3$$$ 和 $$$1$$$。因此,元素 $$$4$$$、$$$5$$$ 和 $$$2$$$ 被删除。
- $$$[3, 1]$$$ 中唯一的局部最大值是 $$$3$$$。因此,元素 $$$1$$$ 被删除。只剩下一个元素;因此该过程终止。
这满足数组 $$$a = [1, -1, 1, 2, 1]$$$,因为元素 $$$p_1 = 4$$$、$$$p_3 = 5$$$ 和 $$$p_5 = 2$$$ 在迭代时被删除 $$$1$$$、元素 $$$p_4 = 1$$$ 在迭代时被删除$$$2$$$,且元素 $$$p_2 = 3$$$ 未被删除。
在第三个测试用例中,将对排列 $$$[6, 7, 2, 4, 3, 8, 5, 1]$$$ 进行运算,如下所示:
- $$$[6, 7, 2, 4, 3, 8, 5, 1]$$$ 中的局部最小值为 $$$6$$$、$$$2$$$、$$$3$$$ 和 $$$1$$$。因此,元素 $$$7$$$、$$$4$$$、$$$8$$$ 和 $$$5$$$ 被删除。
- $$$[6, 2, 3, 1]$$$ 中的局部最大值为 $$$6$$$ 和 $$$3$$$。因此,元素 $$$2$$$ 和 $$$1$$$ 被删除。
- $$$[6, 3]$$$ 中唯一的局部最小值是 $$$3$$$。因此,元素 $$$6$$$ 被删除。只剩下一个元素;因此该过程终止。
在第四个测试用例中,满足约束的一个排列是[$$$6$$$、$$$5$$$、$$$2$$$、$$$1$$$、$$$3$$$、$$$4$$$、$$$7$$$]。 $$$1$$$ 是唯一的局部最小值,因此只有它会在第一次迭代后保留。请注意,还有其他有效的排列;例如,[$$$6$$$, $$$4$$$, $$$3$$$, $$$1$$$, $$$2$$$, $$$5$$$, $$$7$$$] 也将被认为是正确的。