A18742.上一个排列

时间限制：1000ms
内存限制：512MB

在一个虚拟世界中，Macw 是一名寻宝冒险家，他在一本古老的地图上发现了一连串的谜题，每一个谜题都代表着一个宝藏的位置。这些谜题由一串数字排列组成，称为"字典序排列"。Macw 将这个问题带给了你，希望聪明的你能帮助 Macw 解决这道题目。

你将会给到一个名为 $origin$ 的字典序排列和名为 $current$ 的初始排列。

现定义$origin$排列作为按照字典序排序的第一个排列，即定义 $origin[i] < origin[j](1 \le i < j \le n)$，请忽略 $origin[i]$ 的实际数值大小。

你的任务是找出 $current$ 根据 $origin$ 作为第一个按照字典序排列的上一个字典序排列。

举例而言，如果第一个字典序排列 $origin=[1, 2, 3, 4, 5]$，则下一个按照字典序的排列是 $[1, 2, 3, 5, 4]$。

同样地，如果第一个字典序排列 $origin=[1, 3, 5, 6, 2]$，则 $origin$ 的下一个字典序排列为 $[1, 3, 5, 2, 6]$。反之，如果当前排列为 $current=[1, 3, 5, 2, 6]$，若以 $origin$ 作为参考，则上一个字典序排列应为 $[1, 3, 5, 6, 2]$。

输入数据包含三行，
第一行输入一个整数 $n$，代表序列的长度。
第二行输入 $n$ 个不同的整数，表示初始排列，用空格相隔开。
第三行输入 $n$ 个不同的整数，表示当前排列，用空格相隔开。

输出包含一行 $n$ 个整数，用空格相隔开。表示当前排列以初始排列为参考（作为第一个排列）的情况下的上一个排列。

样例解释：
对于第三个样例，若按照 $[8, 5, 7]$ 为字典序的第一个排列，那么按照字典序排列的所有三位数排列如下：

1. $[8, 5, 7]$
2. $[8, 7, 5]$
3. $[5, 8, 7]$
4. $[5, 7, 8]$
5. $[7, 8, 5]$
6. $[7, 5, 8]$

因此，对于给定排列 $[5, 7, 8]$ 来说，上一个排列应改为 $[5, 8, 7]$。

数据范围：
对于100%的数据，保证有解，即 $origin$ 排列和 $current$ 排列不相等。
对于30%的数据，保证 $2 \leq n \leq 9$。
对于100%的数据，保证 $2 \leq n \leq 10^5$。
对于100%的数据，保证给定的序列的任意一项 $1 \leq origin[i], current[i] \leq 10^6$。