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 翻译