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 翻译