Universal Cup Judging System

Universal Cup

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

Une séquence de parenthèses est une chaîne composée des caractères ( et ). Une séquence de parenthèses $s_{1,2,\ldots,m}$ est dite valide si elle vérifie l'une des conditions suivantes :

  • $s$ est vide.
  • $s_1 = $ (, $s_m = $ ), et $s_{2,3,\ldots,m-1}$ est valide.
  • Il existe une position $k$ ($1 \le k < m$) telle que $s_{1,2,\ldots,k}$ est valide et $s_{k+1,k+2,\ldots,m}$ est valide.

Deux positions $i, j$ ($1 \le i < j \le m$) dans la séquence de parenthèses $s_{1,2,\ldots,m}$ sont dites appariées si et seulement si $s_{i,i+1,\ldots,j}$ et $s_{i+1,i+2,\ldots,j-1}$ sont toutes deux valides.

On vous donne une suite d'entiers de longueur $n$, $a_1, a_2, \ldots, a_n$, où $n$ est garanti pair. Nous construisons une nouvelle suite d'entiers $c_1, c_2, \ldots, c_n$ à l'aide d'une séquence de parenthèses valide $b_1, b_2, \ldots, b_n$, telle que $\forall 1 \le i \le n, c_i = a_{p_i}$, où $p_i$ est la position appariée avec la position $i$ dans $b_{1,2,\ldots,n}$.

Trouvez une séquence de parenthèses valide $b_{1,2,\ldots,n}$ telle que l'ordre lexicographique de $c_{1,2,\ldots,n}$ soit minimisé. S'il existe plusieurs solutions, affichez l'une quelconque d'entre elles.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 2.5 \times 10^5$), indiquant le nombre de cas de test.

Pour chaque cas de test :

La première ligne contient un entier $n$ ($1 \le n \le 5 \times 10^5$), indiquant la longueur de la suite $a$, et il est garanti que $n$ est pair.

La deuxième ligne contient $n$ entiers séparés par des espaces, représentant $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).

Il est garanti que la somme des $n$ ne dépasse pas $5 \times 10^5$.

Sortie

Pour chaque cas de test, affichez une ligne contenant une chaîne de longueur $n$, représentant $b_{1,2,\ldots,n}$.

Exemples

Entrée 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

Sortie 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.