Universal Cup Judging System

Universal Cup

Time Limit: 1.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

괄호열은 문자 (와 )로 이루어진 문자열입니다. 괄호열 $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

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.