/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ 2N の文字列 S=S_1S_2\dots S_{2N} について、 S が N 個の ( , および N 個の ) で構成されるとき、 S は「括弧列」であるといいます。
また、「括弧列」S のうち、以下のいずれかに該当するものを「正しい括弧列」といいます。
- 空文字列
- ある「正しい括弧列」A が存在して
(, A,)をこの順に連結した文字列 - ある空でない「正しい括弧列」A,\ B が存在して、 A,\ B をこの順に連結した文字列
1 から 2N までの整数からなる 2 つの順列 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
存在する場合は 1 つ求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P_i,Q_i \leq 2N
- P,\ Q はそれぞれ 1 から 2N までの整数の順列
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N
P_1 P_2 \dots P_{2N}
Q_1 Q_2 \dots Q_{2N}
出力
上記のような「括弧列」S が存在する場合、そのうち 1 つを出力してください。答えが複数存在する場合はいずれを出力してもかまいません。
存在しない場合は -1 を出力してください。
入力例 1
2 1 2 4 3 4 3 1 2
出力例 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
2 1 3 2 4 4 3 2 1
出力例 2
-1
条件を満たす S は存在しません。
入力例 3
3 2 1 5 3 4 6 6 5 3 4 2 1
出力例 3
-1
Score : 600 points
Problem Statement
A string of length 2N, S=S_1S_2\dots S_{2N}, is said to be a parenthesis sequence when S is composed of N (s and N )s.
Additionally, a parenthesis sequence S is said to be correct when it is one of the following.
- An empty string.
- The concatenation of
(, A,)in this order, where A is a correct parenthesis sequence. - The concatenation of A, B in this order, where A and B are non-empty correct parenthesis sequences.
You are given two permutations P=(P_1,\ P_2,\ \dots,\ P_{2N}) and Q=(Q_1,\ Q_2,\ \dots,\ Q_{2N}) of the integers from 1 to 2N.
Determine whether there exists a parenthesis sequence S=S_1S_2\dots S_{2N} that satisfies the following conditions.
- P is the lexicographically smallest permutation p of the integers from 1 to 2N such that S_{p_1}S_{p_2}\dots S_{p_{2N}} is a correct parenthesis sequence.
- Q is the lexicographically largest permutation p of the integers from 1 to 2N such that S_{p_1}S_{p_2}\dots S_{p_{2N}} is a correct parenthesis sequence.
If such a parenthesis sequence exists, find one.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P_i,Q_i \leq 2N
- Each of P and Q is a permutation of 1 to 2N.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
P_1 P_2 \dots P_{2N}
Q_1 Q_2 \dots Q_{2N}
Output
If there exists a parenthesis sequence S that satisfies the conditions above, print one such sequence. If there are multiple such sequences, you may print any of them.
If there is no such sequence, print -1.
Sample Input 1
2 1 2 4 3 4 3 1 2
Sample Output 1
())(
For S= ())(, some of the permutations p such that S_{p_1}S_{p_2}S_{p_3}S_{p_4} is a correct parenthesis sequence are p=(1,\ 4,\ 2,\ 3),\ (1,\ 4,\ 3,\ 2). The lexicographically smallest and largest among them are p=(1,\ 2,\ 4,\ 3) and p=(4,\ 3,\ 1,\ 2), satisfying the conditions.
Sample Input 2
2 1 3 2 4 4 3 2 1
Sample Output 2
-1
No S satisfies the conditions.
Sample Input 3
3 2 1 5 3 4 6 6 5 3 4 2 1
Sample Output 3
-1