← 返回题目列表

AtCoder · arc120_d

D. 括号分数 2

中文机器翻译题面 查看原题

分数: 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

因此,在这种情况下,两者都是有效答案。