共有 $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

()(())()