$2n$ 個の要素が $n$ 個のペアに分かれている。

各ペアについて、両方の要素に開き括弧を割り当てるか、両方の要素に閉じ括弧を割り当てる必要がある。結果として得られる括弧の列を正しい括弧列にするか、それが不可能であることを判定せよ。複数の解が存在する場合は、辞書順で最小の文字列（$2n$ 個の括弧からなり、'(' は ')' より小さいとする）となる解を求めよ。

入力

1行目に整数 $n$ ($1 \le n \le 200\,000$) が与えられる。 2行目に $2n$ 個の整数 $p_1, p_2, \dots, p_{2n}$ ($1 \le p_i \le n$) が与えられる。$1$ から $n$ までのすべての整数が、この列の中にちょうど2回ずつ現れる。

出力

各ペアに対して括弧の種類を選択して正しい括弧列を作ることが不可能な場合は、"("（ロシア語の悲しい顔文字）を出力せよ。可能な場合は、辞書順で最小の正しい括弧列を出力せよ。

入出力例

入力 1

2
1 2 1 2

出力 1

()()

入力 2

1
1 1

出力 2

(

入力 3

4
4 3 1 2 3 2 1 4

出力 3

(

入力 4

4
3 1 2 1 4 3 2 4

出力 4

(()()())

入力 5

4
2 4 3 1 3 4 2 1

出力 5

()()()()

入力 6

4
4 4 3 3 1 2 1 2

出力 6

(((())))

入力 7

4
1 3 1 2 4 4 2 3

出力 7

()(())()