配点 : $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$ つ出力せよ。 正しい答えが複数存在する場合、どれを出力しても正解と判定される。

2
1 2 3 4

(())

長さ $4$ の括弧の対応が取れている文字列は (()) と ()() の $2$ 種類あり、それぞれのスコアは以下の通りです。

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

よって、(()) のみが正しい答えとなります。

2
2 3 2 3

()()

(()) と ()() のスコアは以下の通りです。

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

よって、この場合どちらを出力しても正解となります。