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.