共有 $2n$ 個元素被分為 $n$ 對。

對於每一對，你必須將左括號分配給這兩個元素，或是將右括號分配給這兩個元素。你需要使產生的括號序列成為一個合法的括號序列，或者判斷這是不可能的。如果存在多種可能的解，請找出字典序最小的字串（由 $2n$ 個括號組成，'(' 小於 ')'）。

輸入格式

第一行包含一個整數 $n$ ($1 \le n \le 200\,000$)。

下一行包含 $2n$ 個整數 $p_1, p_2, \dots, p_{2n}$ ($1 \le p_i \le n$)。序列中從 $1$ 到 $n$ 的所有整數皆恰好出現兩次。

輸出格式

如果無法為每一對選擇一種括號類型以使產生的括號序列合法，請輸出 "("（俄語的悲傷表情符號）。否則，請輸出字典序最小的合法括號序列。

範例

輸入格式 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

()(())()