Brackets

Time limit1sMemory limit512 MB

Summary

Each value's two positions must both be '(' or both be ')' so the result is a valid bracket sequence. Print the lexicographically smallest one, or the sad smiley if none exists.

Level: Medium7 of 10
Topics: Greedy, Segment tree, String
Solved: No attempts yet

Problem

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

For each pair, you must assign an opening bracket to both elements, or a closing bracket to both elements. The resulting bracket sequence must be a correct bracket sequence. If that is impossible, report it. If several assignments work, output the lexicographically smallest resulting string, where '(' is smaller than ')'.

Input

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$ ). Each integer from $1$ to $n$ appears exactly twice in this sequence.

Output

If no valid assignment exists, print '(' (the Russian sad smiley). Otherwise, print the lexicographically smallest correct bracket sequence of length $2n$ .

Examples5

Example 1
Input
```
2
1 2 1 2
```
Expected output
```
()()
```
Example 2
Input
```
1
1 1
```
Expected output
```
(
```
Example 3
Input
```
4
4 3 1 2 3 2 1 4
```
Expected output
```
(
```
Example 4
Input
```
4
3 1 2 1 4 3 2 4
```
Expected output
```
(()()())
```
Example 5
Input
```
4
2 4 3 1 3 4 2 1
```
Expected output
```
()()()()
```