#P17904. Parentheses and Swapping
Parentheses and Swapping
给定偶数长度 的整数数组 。请构造一个长度为 的合法括号序列 。
合法括号序列由 (、) 构成,左右括号总数相等,并且任意前缀中左括号数不少于右括号数。匹配关系按通常的栈规则确定:每个右括号匹配它左边最近的尚未匹配的左括号。
对于 中每一对匹配位置 ,交换 。所有位置恰好参加一次交换,得到数组 。
你需要让 的字典序尽可能小,并输出对应的括号序列。字典序比较时,找到第一个不同的位置,该位置元素较小的数组更小。
输入格式
第一行给出测试组数 ,。
每组测试占两行:第一行给出偶数 ,;第二行给出 个整数 ,。
整个输入文件满足 。数组元素允许重复。
输出格式
每组测试输出一行长度为 的合法括号序列。若有多个能得到最小数组的序列,任意输出一个即可。
样例 1
输入
5
6
4 1 5 4 1 1
4
1 2 3 2
4
1 3 1 2
2
2 1
8
8 5 2 6 1 4 3 7
输出
((()))
()()
(())
()
((()))()