AT_tupc2022_h.Next Permutation

将 $ (1,2,\ldots,N) $ 的排列在下文中称为“顺序排列”。

对于一个排列 $ P $，定义 $ \mathrm{NextPermutation}(P) $ 如下：

• 当 $ P=(N,N-1,\ldots,2,1) $ 时，$\mathrm{NextPermutation}(P) = (1,2,\ldots,N-1,N)$；
• 否则，$ \mathrm{NextPermutation}(P) $ 是将所有长度为 $ N $ 的排列按字典序升序排列后，$ P $ 的下一个排列。

给定两个排列 $ P=(P_1, P_2, \ldots,P_N),\ Q=(Q_1, Q_2, \ldots, Q_N) $。

不断进行如下操作，直到 $ P $ 等于 $ (1,2,\ldots, N-1,N) $ 为止：

• 用 $ \mathrm{NextPermutation}(P) $ 替换 $ P $，用 $ \mathrm{NextPermutation}(Q) $ 替换 $ Q $。

请你求出最终得到的 $ Q $。

输入为一行，包含：

$ N\ P_1\ P_2\ \ldots\ P_N\ Q_1\ Q_2\ \ldots\ Q_N $

请将最终得到的排列 $ Q'=(Q'_1,Q'_2,\ldots,Q'_N) $ 的每个数以空格分隔输出。

样例解释1

通过操作，$ P,Q $ 会如下变化：

• $ P $ ： $ (2,3,1)\to (3,1,2)\to (3,2,1)\to (1,2,3) $
• $ Q $ ： $ (3,2,1)\to (1,2,3)\to (1,3,2)\to (2,1,3) $

样例解释2

通过操作，$ P,Q $ 会如下变化：

• $ P $ ： $ (4,2,1,3)\to (4,2,3,1)\to (4,3,1,2)\to (4,3,2,1)\to(1,2,3,4) $
• $ Q $ ： $ (2,1,3,4)\to(2,1,4,3)\to(2,3,1,4)\to(2,3,4,1)\to(2,4,1,3) $

样例解释3

一次操作都不执行。

数据范围

• $ 2\leq N\leq 2\times 10^5 $
• $ (P_1, P_2, \ldots,P_N),(Q_1, Q_2, \ldots, Q_N) $ 均为 $ (1,2,\ldots,N) $ 的排列
• 输入均为整数

由 ChatGPT 5 翻译