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}$ 是合法的。
  • 存在一個位置 $k$ ($1 \le k < m$),使得 $s_{1,2,\ldots,k}$ 是合法的,且 $s_{k+1,k+2,\ldots,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$ 匹配的位置。

請找出一個合法的括號序列 $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

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

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.