AT_arc120_d.[ARC120D] Bracket Score 2

我们将括号匹配的字符串定义为满足以下任一条件的字符串：

• 空字符串。
• 存在某些括号匹配的非空字符串 $s,\ t$，将 $s$ 和 $t$ 按顺序连接得到的字符串。
• 存在某个括号匹配的字符串 $s$，将 (、$s$、) 按顺序连接得到的字符串。

此外，对于括号匹配的字符串 $s$，我们称 $s$ 的第 $i$ 个字符和第 $j$ 个字符匹配，当且仅当满足以下所有条件：

• $1 \le i < j \le |s|$。
• $s_i = $ (。
• $s_j = $ )。
• $s$ 的第 $i$ 个字符和第 $j$ 个字符之间的子串（不包括 $i$ 和 $j$ 这两个字符）是一个括号匹配的字符串。

给定一个长度为 $2N$ 的数列 $A = (A_1, A_2, A_3, \dots, A_{2N})$。
对于长度为 $2N$ 的括号匹配的字符串 $s$，定义其得分为：对所有 $s$ 中匹配的字符对 $(i, j)$，将 $|A_i - A_j|$ 的值累加起来。

请你求出所有长度为 $2N$ 的括号匹配的字符串中，得分最大的一个字符串。输出任意一个即可。

输入以如下格式从标准输入读入：

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

请输出一个长度为 $2N$ 的括号匹配的字符串，使其得分最大。
如果有多个答案，输出其中任意一个均可。

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• 输入中的所有值均为整数。

样例解释 1

长度为 $4$ 的括号匹配的字符串有两种：(()) 和 ()()，它们的得分如下：

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

因此，只有 (()) 是正确答案。

样例解释 2

(()) 和 ()() 的得分如下：

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

因此，这种情况下输出任意一个都是正确答案。

由 ChatGPT 4.1 翻译