← 返回题目列表

AtCoder · arc141_c

C. 括号和排列

中文机器翻译题面 查看原题

分数: 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