괄호열은 문자 (와 )로 이루어진 문자열입니다. 괄호열 $s_{1,2,\ldots,m}$이 다음 조건 중 하나를 만족하면 올바른 괄호열이라고 정의합니다:
- $s$가 빈 문자열입니다.
- $s_1 = $
(, $s_m = $)이고, $s_{2,3,\ldots,m-1}$이 올바른 괄호열입니다. - $s_{1,2,\ldots,k}$가 올바른 괄호열이고 $s_{k+1,k+2,\ldots,m}$이 올바른 괄호열이 되도록 하는 위치 $k$ ($1 \le k < m$)가 존재합니다.
괄호열 $s_{1,2,\ldots,m}$에서 두 위치 $i, j$ ($1 \le i < j \le m$)는 $s_{i,i+1,\ldots,j}$와 $s_{i+1,i+2,\ldots,j-1}$이 모두 올바른 괄호열일 때 그리고 그때에만 서로 매칭된다고 합니다.
길이가 $n$인 정수 수열 $a_1, a_2, \ldots, a_n$이 주어지며, $n$은 짝수임이 보장됩니다. 우리는 올바른 괄호열 $b_1, b_2, \ldots, b_n$을 통해 새로운 정수 수열 $c_1, c_2, \ldots, c_n$을 구성하는데, 이는 $\forall 1 \le i \le n, c_i = a_{p_i}$를 만족합니다. 여기서 $p_i$는 $b_{1,2,\ldots,n}$에서 위치 $i$와 매칭되는 위치입니다.
$c_{1,2,\ldots,n}$이 사전순으로 가장 작아지도록 하는 올바른 괄호열 $b_{1,2,\ldots,n}$을 구하십시오. 가능한 해가 여러 개라면 그중 아무것이나 출력하십시오.
입력
첫째 줄에 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 2.5 \times 10^5$)가 주어집니다.
각 테스트 케이스에 대하여:
첫째 줄에 수열 $a$의 길이를 나타내는 정수 $n$ ($1 \le n \le 5 \times 10^5$)이 주어지며, $n$은 짝수임이 보장됩니다.
둘째 줄에 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$)을 나타내는 공백으로 구분된 $n$개의 정수가 주어집니다.
모든 테스트 케이스에서 $n$의 합은 $5 \times 10^5$을 넘지 않음이 보장됩니다.
출력
각 테스트 케이스마다 $b_{1,2,\ldots,n}$을 나타내는 길이 $n$인 문자열을 한 줄에 출력합니다.
예제
입력 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
출력 1
((())) ()() (()) () ((()))()