← 返回题目列表

Codeforces · 2103/D

D. 当地建设

中文机器翻译题面 查看原题

如果至少满足以下条件之一,则数组 $$$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$$$ 的排列元素。

如果有多个解,则可以输出其中任何一个。

示例

输入
复制

7
3
1 1 -1
5
1 -1 1 2 1
8
3 1 2 1 -1 1 1 2
7
1 1 1 -1 1 1 1
5
1 1 1 1 -1
5
-1 1 1 1 1
5
-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]$$$,如下所示:

  1. $$$[3, 2, 1]$$$ 中唯一的局部最小值是 $$$1$$$。因此,元素 $$$3$$$ 和 $$$2$$$ 被删除。只剩下一个元素;因此该过程终止。

这满足数组 $$$a = [1, 1, -1]$$$,因为 $$$p_1$$$ 和 $$$p_2$$$ 都在迭代编号 $$$1$$$ 上被删除,而 $$$p_3$$$ 未被删除。

在第二个测试用例中,运算将应用于排列 $$$p = [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 = 4$$$、$$$p_3 = 5$$$ 和 $$$p_5 = 2$$$ 在迭代时被删除 $$$1$$$、元素 $$$p_4 = 1$$$ 在迭代时被删除$$$2$$$,且元素 $$$p_2 = 3$$$ 未被删除。

在第三个测试用例中,将对排列 $$$[6, 7, 2, 4, 3, 8, 5, 1]$$$ 进行运算,如下所示:

  1. $$$[6, 7, 2, 4, 3, 8, 5, 1]$$$ 中的局部最小值为 $$$6$$$、$$$2$$$、$$$3$$$ 和 $$$1$$$。因此,元素 $$$7$$$、$$$4$$$、$$$8$$$ 和 $$$5$$$ 被删除。
  2. $$$[6, 2, 3, 1]$$$ 中的局部最大值为 $$$6$$$ 和 $$$3$$$。因此,元素 $$$2$$$ 和 $$$1$$$ 被删除。
  3. $$$[6, 3]$$$ 中唯一的局部最小值是 $$$3$$$。因此,元素 $$$6$$$ 被删除。只剩下一个元素;因此该过程终止。

在第四个测试用例中,满足约束的一个排列是[$$$6$$$、$$$5$$$、$$$2$$$、$$$1$$$、$$$3$$$、$$$4$$$、$$$7$$$]。 $$$1$$$ 是唯一的局部最小值,因此只有它会在第一次迭代后保留。请注意,还有其他有效的排列;例如,[$$$6$$$, $$$4$$$, $$$3$$$, $$$1$$$, $$$2$$$, $$$5$$$, $$$7$$$] 也将被认为是正确的。