分数: 600 点
问题陈述
长度的字符串 2N, S=S_1S_2\dots S_{2N},据说是 括号序列 当 S 组成 N (和 N )s。
另外,括号序列 S 据说是 正确 当它是以下之一时。
- 空字符串。
- 的串联
(, A,)按此顺序,其中 A 是正确的括号序列。 - 的串联 A, B 按此顺序,其中 A 和 B 是非空的正确括号序列。
给你两种排列 P=(P_1,\ P_2,\ \dots,\ P_{2N}) 和 Q=(Q_1,\ Q_2,\ \dots,\ Q_{2N}) 中的整数 1 to 2N.
判断是否存在括号序列 S=S_1S_2\dots S_{2N} 满足以下条件。
- P 是字典顺序上最小的排列 p 中的整数 1 to 2N 这样 S_{p_1}S_{p_2}\dots S_{p_{2N}} 是正确的括号序列。
- Q 是字典顺序上最大的排列 p 中的整数 1 to 2N 这样 S_{p_1}S_{p_2}\dots S_{p_{2N}} 是正确的括号序列。
如果存在这样的括号序列,请找到一个。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P_i,Q_i \leq 2N
- 每个 P 和 Q 是一个排列 1 to 2N.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
P_1 P_2 \dots P_{2N}
Q_1 Q_2 \dots Q_{2N}
输出
如果存在括号序列 S 满足上述条件,打印一个这样的序列。如果有多个这样的序列,您可以打印其中任何一个。
如果没有这样的序列,则打印 -1.
示例输入 1
2 1 2 4 3 4 3 1 2
示例输出 1
())(
对于 S= ())(,一些排列 p 这样 S_{p_1}S_{p_2}S_{p_3}S_{p_4} 是正确的括号序列 p=(1,\ 4,\ 2,\ 3),\ (1,\ 4,\ 3,\ 2)。其中按字典顺序最小和最大的是 p=(1,\ 2,\ 4,\ 3) 和 p=(4,\ 3,\ 1,\ 2),满足条件。
示例输入 2
2 1 3 2 4 4 3 2 1
示例输出 2
-1
No S 满足条件。
示例输入 3
3 2 1 5 3 4 6 6 5 3 4 2 1
示例输出 3
-1