AT_arc141_c.[ARC141C] Bracket and Permutation

对于一个长度为 $2N$ 的字符串 $S=S_1S_2\dots S_{2N}$，如果 $S$ 由 $N$ 个 ( 和 $N$ 个 ) 组成，则称 $S$ 为“括号列”。

此外，在“括号列”$S$ 中，满足以下任一条件的称为“正确的括号列”：

• 空字符串；
• 存在某个“正确的括号列”$A$，将 (、$A$、) 按此顺序连接得到的字符串；
• 存在非空的“正确的括号列”$A,B$，将 $A,B$ 按此顺序连接得到的字符串。

给定两个由 $1$ 到 $2N$ 的整数构成的排列 $P=(P_1,P_2,\dots,P_{2N})$ 和 $Q=(Q_1,Q_2,\dots,Q_{2N})$。

请判断是否存在一个“括号列”$S=S_1S_2\dots S_{2N}$，满足以下条件：

• 在所有使得 $S_{p_1}S_{p_2}\dots S_{p_{2N}}$ 为“正确的括号列”的 $1$ 到 $2N$ 的排列 $p$ 中，字典序最小的为 $P$；
• 在所有使得 $S_{p_1}S_{p_2}\dots S_{p_{2N}}$ 为“正确的括号列”的 $1$ 到 $2N$ 的排列 $p$ 中，字典序最大的为 $Q$。

如果存在这样的 $S$，请输出其中任意一个。如果不存在，请输出 -1。

输入以如下格式从标准输入读入：

$N$ $P_1$ $P_2$ $\dots$ $P_{2N}$ $Q_1$ $Q_2$ $\dots$ $Q_{2N}$

如果存在满足条件的“括号列”$S$，请输出其中任意一个。如果有多个答案，可以输出任意一个。

如果不存在，请输出 -1。

限制

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq P_i, Q_i \leq 2N$
• $P,Q$ 分别是 $1$ 到 $2N$ 的整数的排列
• 输入的所有值均为整数

样例解释 1

当 $S=$ ())( 时，$S_{p_1}S_{p_2}S_{p_3}S_{p_4}$ 能成为“正确的括号列”的 $p$ 有 $p=(1,4,2,3),(1,4,3,2)$ 等，其中字典序最小的是 $p=(1,2,4,3)$，最大的是 $p=(4,3,1,2)$，因此 $S$ 满足条件。

样例解释 2

不存在满足条件的 $S$。

由 ChatGPT 4.1 翻译