{"raw_statement":[{"iden":"problem statement","content":"Let us define **balanced parenthesis string** as a string satisfying one of the following conditions:\n\n*   An empty string.\n*   A concatenation of $s$ and $t$ in this order, for some non-empty balanced parenthesis strings $s$ and $t$.\n*   A concatenation of `(`, $s$, `)` in this order, for some balanced parenthesis string $s$.\n\nAlso, 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:\n\n*   $1 \\le i < j \\le |s|$.\n*   $s_i = $ `(`.\n*   $s_j = $ `)`.\n*   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.\n\nYou are given a sequence of length $2N$: $A = (A_1, A_2, A_3, \\dots, A_{2N})$.  \nLet 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.\nAmong the balanced parenthesis strings of length $2N$, find one with the maximum score."},{"iden":"constraints","content":"*   $1 \\le N \\le 2 \\times 10^5$\n*   $1 \\le A_i \\le 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $A_3$ $\\dots$ $A_{2N}$"},{"iden":"sample input 1","content":"2\n1 2 3 4"},{"iden":"sample output 1","content":"(())\n\nThere are two balanced parenthesis strings of length $4$: `(())` and `()()`, with the following scores:\n\n*   `(())`: $|1 - 4| + |2 - 3| = 4$\n*   `()()`: $|1 - 2| + |3 - 4| = 2$\n\nThus, `(())` is the only valid answer."},{"iden":"sample input 2","content":"2\n2 3 2 3"},{"iden":"sample output 2","content":"()()\n\n`(())` and `()()` have the following scores:\n\n*   `(())` : $|2 - 3| + |3 - 2| = 2$\n*   `()()` : $|2 - 3| + |2 - 3| = 2$\n\nThus, either is a valid answer in this case."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}