配点 : $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 を出力してください。

2
1 2 4 3
4 3 1 2

())(

$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
1 3 2 4
4 3 2 1

-1

条件を満たす $S$ は存在しません。

3
2 1 5 3 4 6
6 5 3 4 2 1

-1