题目描述

括弧の対応が取れている文字列を、次のうちいずれかの条件を満たす文字列と定義します。

• 空文字列
• ある括弧の対応が取れている空でない文字列 $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$ つ求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $A_3$ $\dots$ $A_{2N}$

输出格式

長さ $2N$ の括弧の対応が取れている文字列のうち、スコアが最大となるような文字列を $1$ つ出力せよ。
正しい答えが複数存在する場合、どれを出力しても正解と判定される。

题目大意

定义一个合法括号序列的权值为 $\sum |a_i-a_j|$，其中 $(i,j)$ 满足第 $i,j$ 位在括号序列中是配对的。

给定长度为 $2n$ 的序列 $a$，请求出长度为 $2n$ 的权值最大的合法括号序列（不是输出权值，而是输出任意一个解）

translated by

2
1 2 3 4

(())

2
2 3 2 3

()()

提示

制約

• $1\ \le\ N\ \le\ 2\ \times\ 10^5$
• $1\ \le\ A_i\ \le\ 10^9$
• 入力に含まれる値は全て整数

Sample Explanation 1

長さ $4$ の括弧の対応が取れている文字列は (()) と ()() の $2$ 種類あり、それぞれのスコアは以下の通りです。 - (()) : $|1\ -\ 4|\ +\ |2\ -\ 3|\ =\ 4$ - ()() : $|1\ -\ 2|\ +\ |3\ -\ 4|\ =\ 2$ よって、(()) のみが正しい答えとなります。

Sample Explanation 2

(()) と ()() のスコアは以下の通りです。 - (()) : $|2\ -\ 3|\ +\ |3\ -\ 2|\ =\ 2$ - ()() : $|2\ -\ 3|\ +\ |2\ -\ 3|\ =\ 2$ よって、この場合どちらを出力しても正解となります。