题目描述

我们定义平衡括号字符串为满足以下条件之一的字符串：

• 空字符串。
• 对于一些非空的平衡括号字符串 $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 \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$

因此，在这种情况下，任何一个都是有效答案。