18908번 - Brackets 다국어

There are $2n$ elements divided into $n$ pairs.

For each pair, you should either assign an opening bracket to both elements, or closing bracket to both elements. You need to make the resulting sequence of brackets a correct bracket sequence or determine that it is impossible. If there are several possible solutions, find the solution with the smallest lexicographically string (of $2n$ brackets, '(' is smaller than ')').

The first line contains one integer $n$ ($1 \leq n \leq 200\,000$).

The next line contains $2n$ integers, $p_1, p_2, \ldots, p_{2n}$ ($1 \leq p_i \leq n$). All integers from $1$ to $n$ appear exactly two times in this sequence.

If it is impossible to choose one type of bracket for each pair to make the derived bracket sequence correct, print "(" (Russian sad smiley). Otherwise, print the desired lexicographically minimal correct bracket sequence.