F. Skyscape
constructive algorithms; data structures; greedy
You are given a permutation \(a\) of length \(n\)\(^{\text{∗}}\).We say that a permutation \(b\) of length \(n\) is good if the two permutations \(a\) and \(b\) can become the same after performing the following operation at most \(n\) times (possibly zero): Choose two integers \(l, r\) such that \(1 \le l < r \le n\) and \(a_r = \min(a_l, a_{l + 1}, \ldots, a_r)\). Cyclically shift the subsegment \([a_l, a_{l + 1}, \ldots, a_r]\) one position to the right. In other words, replace \(a\) with \([a_1, \ldots, a_{l - 1}, \; a_r, a_l, a_{l + 1}, \ldots, a_{r - 1}, \; a_{r + 1}, \ldots, a_n]\). You are also given a permutation \(c\) of length \(n\) where some elements are missing and represented by \(0\).You need to find a good permutation \(b_1, b_2, \ldots, b_n\) such that \(b\) can be formed by filling in the missing elements of \(c\) (i.e., for all \(1 \le i \le n\), if \(c_i \ne 0\), then \(b_i = c_i\)). If it is impossible, output \(-1\).\(^{\text{∗}}\)A permutation of length \(n\) is an array consisting of \(n\) distinct integers from \(1\) to \(n\) in arbitrary order. For example, \([2,3,1,5,4]\) is a permutation, but \([1,2,2]\) is not a permutation (\(2\) appears twice in the array), and \([1,3,4]\) is also not a permutation (\(n=3\) but there is \(4\) in the array).
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \le t \le 10^4\)). The description of the test cases follows. The first line of each test case contains a single integer \(n\) (\(2 \le n \le 5 \cdot 10^5\)).The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)). It is guaranteed that \(a\) is a permutation of length \(n\).The third line of each test case contains \(n\) integers \(c_1, c_2, \ldots, c_n\) (\(0 \le c_i \le n\)). It is guaranteed that the elements of \(c\) that are not \(0\) are distinct.It is guaranteed that the sum of \(n\) over all test cases does not exceed \(5 \cdot 10^5\).
For each test case: If it is impossible to find such a good permutation \(b\), output a single integer \(-1\). Otherwise, output \(n\) integers \(b_1, b_2, \ldots, b_n\) — the good permutation \(b\) you've found. You need to ensure that for all \(1 \le i \le n\), if \(c_i \ne 0\), then \(b_i = c_i\). If there are multiple answers, output any of them.
In the first test case, \(b = [1, 2]\) is a valid answer since after performing the following operation, \(a\) and \(b\) will become the same: Choose \(l = 1, r = 2\) and cyclically shift the subsegment \([a_1, a_2]\) one position to the right. Then \(a\) will become \([1, 2]\). In the second test case, \(b = [2, 3, 4, 1]\) is a valid answer since after performing the following operation, \(a\) and \(b\) will become the same: Choose \(l = 1, r = 2\) and cyclically shift the subsegment \([a_1, a_2]\) one position to the right. Then \(a\) will become \([2, 3, 4, 1]\). In the third test case, \(b = [1, 3, 2, 4, 5]\) is a valid answer since after performing the following operation, \(a\) and \(b\) will become the same: Choose \(l = 1, r = 3\) and cyclically shift the subsegment \([a_1, a_2, a_3]\) one position to the right. Then \(a\) will become \([1, 3, 2, 5, 4]\). Choose \(l = 4, r = 5\) and cyclically shift the subsegment \([a_4, a_5]\) one position to the right. Then \(a\) will become \([1, 3, 2, 4, 5]\). In the fourth test case, \(b = [3, 2, 1, 5, 4]\) is a valid answer since \(a\) and \(b\) are already the same.In the fifth test case, it is impossible to find such a good permutation \(b\), so you should output \(-1\).In the sixth test case, \(b = [3, 2, 1, 5, 4, 6]\) is a valid answer since after performing the following operation, \(a\) and \(b\) will become the same: Choose \(l = 2, r = 4\) and cyclically shift the subsegment \([a_2, a_3, a_4]\) one position to the right. Then \(a\) will become \([3, 2, 5, 6, 1, 4]\). Choose \(l = 3, r = 5\) and cyclically shift the subsegment \([a_3, a_4, a_5]\) one position to the right. Then \(a\) will become \([3, 2, 1, 5, 6, 4]\). Choose \(l = 5, r = 6\) and cyclically shift the subsegment \([a_5, a_6]\) one position to the right. Then \(a\) will become \([3, 2, 1, 5, 4, 6]\).