CF1611C Polycarp Recovers the Permutation

Polycarp 在白板上写下了一个长度为 $n$ 的数组 $p$，它是 $1$ 到 $n$ 的一个排列。换句话说，在 $p$ 中，每个 $1$ 到 $n$ 的数字恰好出现一次。 他还准备了一个结果数组 $a$，初始时为空（即长度为 $0$）。 接下来，他恰好进行了 $n$ 步操作。每一步操作如下： - 查看 $p$ 的最左端和最右端元素，选择其中较小的一个。 - 如果选择了 $p$ 的最左端元素，则将其添加到 $a$ 的最左端；否则，如果选择了 $p$ 的最右端元素，则将其添加到 $a$ 的最右端。 - 被选中的元素从 $p$ 中删除。 注意，在最后一步时，$p$ 只剩下一个元素，这个元素既是最左端也是最右端。在这种情况下，Polycarp 可以自由选择将其作为左端或右端处理。换句话说，这个元素可以被添加到 $a$ 的左端或右端（由 Polycarp 决定）。 让我们看一个例子。设 $n=4$，$p=[3, 1, 4, 2]$。初始时 $a=[]$。然后： - 第一步，最小值在右端（值为 $2$），操作后 $p=[3,1,4]$，$a=[2]$（将 $2$ 添加到右端）。 - 第二步，最小值在左端（值为 $3$），操作后 $p=[1,4]$，$a=[3,2]$（将 $3$ 添加到左端）。 - 第三步，最小值在左端（值为 $1$），操作后 $p=[4]$，$a=[1,3,2]$（将 $1$ 添加到左端）。 - 第四步，最小值既是左端也是右端（值为 $4$）。假设 Polycarp 选择右端。操作后 $p=[]$，$a=[1,3,2,4]$（将 $4$ 添加到右端）。 因此，经过 $n$ 步操作后，$a$ 的一种可能取值为 $a=[1,3,2,4]$。 现在给定最终得到的数组 $a$，请你找出任意一种可能的初始数组 $p$，使得经过上述过程后能得到给定的 $a$，或者判断无解。

输入的第一行为一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例包含两行。第一行为一个整数 $n$（$1 \le n \le 2\cdot10^5$），表示数组 $a$ 的长度。第二行为 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），表示数组 $a$ 的元素。所有 $a$ 中的元素互不相同。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

输出 $t$ 行，每行对应一个测试用例的答案：$p_1, p_2, \dots, p_n$，表示任意一种可能的初始数组 $p$，使得经过上述过程后能得到给定的 $a$。$p$ 必须是 $1$ 到 $n$ 的一个排列。如果无解，输出 $-1$。

样例中的第一个测试用例已在题目描述中详细说明。对于该测试用例，可能还有其他正确答案。 第二个测试用例中，$n=1$。因此，唯一可能的排列为 $p=[1]$。确实，这是该测试用例的答案。 第三个测试用例，无论选择什么排列 $p$，经过 $n$ 步操作后，得到的结果都不会是 $a=[1, 3, 5, 4, 2]$。 由 ChatGPT 4.1 翻译