CF2084F Skyscape

给定一个长度为 $n$ 的排列 $a$ $^{\text{∗}}$。 我们称一个长度为 $n$ 的排列 $b$ 是好的，如果在最多进行 $n$ 次（可以是零次）以下操作后，排列 $a$ 和 $b$ 可以变得相同： - 选择两个整数 $l, r$，满足 $1 \le l < r \le n$ 且 $a_r = \min(a_l, a_{l + 1}, \ldots, a_r)$。 - 将子段 $[a_l, a_{l + 1}, \ldots, a_r]$ 循环右移一位。换句话说，将 $a$ 替换为： $$ [a_1, \ldots, a_{l - 1}, \; a_r, a_l, a_{l + 1}, \ldots, a_{r - 1}, \; a_{r + 1}, \ldots, a_n] $$ 同时给定一个长度为 $n$ 的排列 $c$，其中部分元素缺失（用 $0$ 表示）。 你需要找到一个好的排列 $b_1, b_2, \ldots, b_n$，使得 $b$ 可以通过填充 $c$ 中缺失的元素得到（即对于所有 $1 \le i \le n$，如果 $c_i \ne 0$，则 $b_i = c_i$）。如果不存在这样的排列，输出 $-1$。 $^{\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 5 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。保证 $a$ 是一个长度为 $n$ 的排列。 第三行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$0 \le c_i \le n$）。保证 $c$ 中非 $0$ 的元素互不相同。 保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

对于每个测试用例： - 如果无法找到满足条件的好排列 $b$，输出一个整数 $-1$。 - 否则，输出 $n$ 个整数 $b_1, b_2, \ldots, b_n$——你找到的好排列 $b$。需要确保对于所有 $1 \le i \le n$，如果 $c_i \ne 0$，则 $b_i = c_i$。如果有多个解，输出任意一个即可。

- 在第一个测试用例中，$b = [1, 2]$ 是一个有效解，因为进行以下操作后 $a$ 和 $b$ 会变得相同： - 选择 $l = 1, r = 2$ 并循环右移子段 $[a_1, a_2]$。此时 $a$ 变为 $[1, 2]$。 - 在第二个测试用例中，$b = [2, 3, 4, 1]$ 是一个有效解，因为进行以下操作后 $a$ 和 $b$ 会变得相同： - 选择 $l = 1, r = 2$ 并循环右移子段 $[a_1, a_2]$。此时 $a$ 变为 $[2, 3, 4, 1]$。 - 在第三个测试用例中，$b = [1, 3, 2, 4, 5]$ 是一个有效解，因为进行以下操作后 $a$ 和 $b$ 会变得相同： - 选择 $l = 1, r = 3$ 并循环右移子段 $[a_1, a_2, a_3]$。此时 $a$ 变为 $[1, 3, 2, 5, 4]$。 - 选择 $l = 4, r = 5$ 并循环右移子段 $[a_4, a_5]$。此时 $a$ 变为 $[1, 3, 2, 4, 5]$。 - 在第四个测试用例中，$b = [3, 2, 1, 5, 4]$ 是一个有效解，因为 $a$ 和 $b$ 已经相同。 - 在第五个测试用例中，不存在满足条件的好排列 $b$，因此输出 $-1$。 - 在第六个测试用例中，$b = [3, 2, 1, 5, 4, 6]$ 是一个有效解，因为进行以下操作后 $a$ 和 $b$ 会变得相同： - 选择 $l = 2, r = 4$ 并循环右移子段 $[a_2, a_3, a_4]$。此时 $a$ 变为 $[3, 2, 5, 6, 1, 4]$。 - 选择 $l = 3, r = 5$ 并循环右移子段 $[a_3, a_4, a_5]$。此时 $a$ 变为 $[3, 2, 1, 5, 6, 4]$。 - 选择 $l = 5, r = 6$ 并循环右移子段 $[a_5, a_6]$。此时 $a$ 变为 $[3, 2, 1, 5, 4, 6]$。 翻译由 DeepSeek V3 完成