#P17904. Parentheses and Swapping

Parentheses and Swapping

给定偶数长度 nn 的整数数组 aa。请构造一个长度为 nn 的合法括号序列 bb。

合法括号序列由 (、) 构成,左右括号总数相等,并且任意前缀中左括号数不少于右括号数。匹配关系按通常的栈规则确定:每个右括号匹配它左边最近的尚未匹配的左括号。

对于 bb 中每一对匹配位置 i,ji,j,交换 ai,aja_i,a_j。所有位置恰好参加一次交换,得到数组 cc。

你需要让 cc 的字典序尽可能小,并输出对应的括号序列。字典序比较时,找到第一个不同的位置,该位置元素较小的数组更小。

输入格式

第一行给出测试组数 TT,1≤T≤2500001\le T\le250000。

每组测试占两行:第一行给出偶数 nn,2≤n≤5000002\le n\le500000;第二行给出 nn 个整数 aia_i,1≤ai≤n1\le a_i\le n。

整个输入文件满足 ∑n≤500000\sum n\le500000。数组元素允许重复。

输出格式

每组测试输出一行长度为 nn 的合法括号序列。若有多个能得到最小数组的序列,任意输出一个即可。

样例 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

输出

((()))
()()
(())
()
((()))()