Скобочная последовательность — это строка, состоящая из символов ( и ). Скобочная последовательность $s_{1,2,\ldots,m}$ называется правильной, если она удовлетворяет одному из следующих условий:
- $s$ пуста.
- $s_1 = $
(, $s_m = $), и $s_{2,3,\ldots,m-1}$ является правильной. - Существует позиция $k$ ($1 \le k < m$) такая, что $s_{1,2,\ldots,k}$ является правильной и $s_{k+1,k+2,\ldots,m}$ является правильной.
Две позиции $i, j$ ($1 \le i < j \le m$) в скобочной последовательности $s_{1,2,\ldots,m}$ называются парными тогда и только тогда, когда как $s_{i,i+1,\ldots,j}$, так и $s_{i+1,i+2,\ldots,j-1}$ являются правильными.
Дана целочисленная последовательность длины $n$: $a_1, a_2, \ldots, a_n$, причём гарантируется, что $n$ чётно. Мы строим новую целочисленную последовательность $c_1, c_2, \ldots, c_n$ с помощью правильной скобочной последовательности $b_1, b_2, \ldots, b_n$ так, что $\forall 1 \le i \le n, c_i = a_{p_i}$, где $p_i$ — позиция, парная позиции $i$ в $b_{1,2,\ldots,n}$.
Найдите правильную скобочную последовательность $b_{1,2,\ldots,n}$, при которой последовательность $c_{1,2,\ldots,n}$ лексикографически минимальна. Если решений несколько, выведите любое из них.
Входные данные
Первая строка содержит целое число $T$ ($1 \le T \le 2.5 \times 10^5$), обозначающее количество наборов входных данных.
Для каждого набора входных данных:
Первая строка содержит целое число $n$ ($1 \le n \le 5 \times 10^5$), обозначающее длину последовательности $a$, причём гарантируется, что $n$ чётно.
Вторая строка содержит $n$ разделённых пробелами целых чисел, представляющих $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
Гарантируется, что сумма $n$ не превосходит $5 \times 10^5$.
Выходные данные
Для каждого набора входных данных выведите строку, содержащую строку длины $n$, представляющую $b_{1,2,\ldots,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
((())) ()() (()) () ((()))()