分数: 600 点
问题陈述
让我们定义 平衡括号字符串 作为满足以下条件之一的字符串:
- 空字符串。
- 的串联 s 和 t 按此顺序,对于一些非空平衡括号字符串 s 和 t.
- 的串联
(, s,)按此顺序,对于一些平衡的括号字符串 s.
另外,我们可以说 i-th 和 j- 括号字符串的第一个字符 s is 对应 当满足以下所有条件时,相互发送 :
- 1 \le i < j \le |s|.
- s_i =
(. - s_j =
). - 之间的字符串 i-th 和 j第一个字符 s,不包括 i-th 和 j- 第一个字符,是一个平衡的括号字符串。
给你一个长度序列 2N: A = (A_1, A_2, A_3, \dots, A_{2N}).
让我们定义
排列的 分数
平衡括号字符串的 平衡括号字符串 s 长度 2N 作为总和 |A_i - A_j| 所有对 (i, j) 这样 i-th 和 j第一个字符 s 彼此对应。
平衡括号字符串长度 2N,找到得分最高的一个。
约束
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 A_3 \dots A_{2N}
输出
打印长度为平衡的括号字符串 2N 得分最高。
如果有多个这样的字符串,则其中任何一个都将被接受。
示例输入 1
2 1 2 3 4
示例输出 1
(())
有两个长度相等的括号字符串 4: (()) 和 ()(),具有以下分数:
(()): |1 - 4| + |2 - 3| = 4()(): |1 - 2| + |3 - 4| = 2
因此, (()) 是唯一有效的答案。
示例输入 2
2 2 3 2 3
示例输出 2
()()
(()) 和 ()() 具有以下分数:
(()): |2 - 3| + |3 - 2| = 2()(): |2 - 3| + |2 - 3| = 2
因此,在这种情况下,两者都是有效答案。