AT_arc043_c.[ARC043C] 転倒距離

将 $1$ 到 $N$ 的整数重新排列得到的数列称为大小为 $N$ 的排列。

对于两个大小相同的排列 $X,\ Y$，在 $X$ 和 $Y$ 中顺序颠倒的数字对的个数称为 $X$ 和 $Y$ 的“逆序距离”。

例如，$[3,\ 1,\ 4,\ 2,\ 5]$ 和 $[2,\ 5,\ 3,\ 4,\ 1]$ 之间有如下 $7$ 个数字对的顺序发生了颠倒，因此它们的逆序距离为 $7$：

• $(1,\ 2),\ (1,\ 4),\ (1,\ 5),\ (2,\ 3),\ (2,\ 4),\ (3,\ 5),\ (4,\ 5)$

给定两个大小为 $N$ 的排列 $A$ 和 $B$。

请判断是否存在一个大小为 $N$ 的排列，使得它与 $A$ 的逆序距离等于它与 $B$ 的逆序距离。如果存在，请给出其中一个排列。

如果有多个答案，可以输出任意一个。

输入通过标准输入按以下格式给出：

$N$
$A_1\ A_2\ \ldots\ A_N$
$B_1\ B_2\ \ldots\ B_N$

• 第 $1$ 行给出一个整数 $N$，表示排列的大小，$1\leq N\leq 10^5$。
• 第 $2$ 行给出排列 $A$ 的 $N$ 个元素，空格分隔。第 $i$ 个整数为 $A$ 的第 $i$ 个元素 $A_i$，$1\leq A_i\leq N$。
• 第 $3$ 行给出排列 $B$ 的 $N$ 个元素，空格分隔。第 $i$ 个整数为 $B$ 的第 $i$ 个元素 $B_i$，$1\leq B_i\leq N$。
• 对于 $i\neq j$，有 $A_i\neq A_j$ 且 $B_i\neq B_j$。

如果不存在满足条件的排列，则输出 $-1$。

如果存在，输出该排列的元素，空格分隔，输出一行。

部分分

本题设置了部分分。

• 对于 $1\leq N\leq 3,000$ 的数据集，答对可得 $30$ 分。
• 对于 $1\leq N\leq 10^5$ 的数据集，答对可再得 $70$ 分，总计 $100$ 分。

样例解释 1

设输出的排列为 $C$，则 $A$ 与 $C$ 的逆序距离和 $B$ 与 $C$ 的逆序距离均为 $5$。

样例解释 2

不存在同时与 $A$ 和 $B$ 具有相同逆序距离的排列。

由 ChatGPT 4.1 翻译