201203: [AtCoder]ARC120 D - Bracket Score 2

Problem Statement

Let us define balanced parenthesis string as a string satisfying one of the following conditions:

• An empty string.
• A concatenation of $s$ and $t$ in this order, for some non-empty balanced parenthesis strings $s$ and $t$.
• A concatenation of (, $s$, ) in this order, for some balanced parenthesis string $s$.

Also, let us say that the $i$-th and $j$-th characters of a parenthesis string $s$ is corresponding to each other when all of the following conditions are satisfied:

• $1 \le i < j \le |s|$.
• $s_i = $ (.
• $s_j = $ ).
• The string between the $i$-th and $j$-th characters of $s$, excluding the $i$-th and $j$-th characters, is a balanced parenthesis string.

You are given a sequence of length $2N$: $A = (A_1, A_2, A_3, \dots, A_{2N})$.
Let us define the score of a balanced parenthesis string $s$ of length $2N$ as the sum of $|A_i - A_j|$ over all pairs $(i, j)$ such that the $i$-th and $j$-th characters of $s$ are corresponding to each other.

Among the balanced parenthesis strings of length $2N$, find one with the maximum score.

Constraints

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $A_3$ $\dots$ $A_{2N}$

Output

Print a balanced parenthesis string of length $2N$ with the maximum score.
If there are multiple such strings, any of them will be accepted.

Sample Input 1

2
1 2 3 4

Sample Output 1

(())

There are two balanced parenthesis strings of length $4$: (()) and ()(), with the following scores:

• (()): $|1 - 4| + |2 - 3| = 4$
• ()(): $|1 - 2| + |3 - 4| = 2$

Thus, (()) is the only valid answer.

Sample Input 2

2
2 3 2 3

Sample Output 2

()()

(()) and ()() have the following scores:

• (()) : $|2 - 3| + |3 - 2| = 2$
• ()() : $|2 - 3| + |2 - 3| = 2$

Thus, either is a valid answer in this case.