Имеется $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

()(())()