/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
括弧の対応が取れている文字列を、次のうちいずれかの条件を満たす文字列と定義します。
- 空文字列
- ある括弧の対応が取れている空でない文字列 s, t が存在し、s, t をこの順に連結した文字列
- ある括弧の対応が取れている文字列 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 文字目が対応しているような全ての組 (i, j) について |A_i - A_j| を足し合わせたものと定義します。
括弧の対応が取れている長さ 2N の文字列のうち、スコアが最大となるような文字列を 1 つ求めてください。
制約
- 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 つ出力せよ。
正しい答えが複数存在する場合、どれを出力しても正解と判定される。
入力例 1
2 1 2 3 4
出力例 1
(())
長さ 4 の括弧の対応が取れている文字列は (()) と ()() の 2 種類あり、それぞれのスコアは以下の通りです。
(()): |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
よって、この場合どちらを出力しても正解となります。
Score : 600 points
Problem Statement
Let us define balanced parenthesis string as a string satisfying one of the following conditions:
- An empty string.
- A concatenation of s and t in this order, for some non-empty balanced parenthesis strings s and t.
- A concatenation of
(, s,)in this order, for some balanced parenthesis string s.
Also, 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:
- 1 \le i < j \le |s|.
- s_i =
(. - s_j =
). - 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.
You are given a sequence of length 2N: A = (A_1, A_2, A_3, \dots, A_{2N}).
Let 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.
Among the balanced parenthesis strings of length 2N, find one with the maximum score.
Constraints
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1 A_2 A_3 \dots A_{2N}
Output
Print a balanced parenthesis string of length 2N with the maximum score.
If there are multiple such strings, any of them will be accepted.
Sample Input 1
2 1 2 3 4
Sample Output 1
(())
There are two balanced parenthesis strings of length 4: (()) and ()(), with the following scores:
(()): |1 - 4| + |2 - 3| = 4()(): |1 - 2| + |3 - 4| = 2
Thus, (()) is the only valid answer.
Sample Input 2
2 2 3 2 3
Sample Output 2
()()
(()) and ()() have the following scores:
(()): |2 - 3| + |3 - 2| = 2()(): |2 - 3| + |2 - 3| = 2
Thus, either is a valid answer in this case.