Universal Cup Judging System

Universal Cup

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

En parentesfølge er en streng sammensatt av tegnene ( og ). En parentesfølge $s_{1,2,\ldots,m}$ defineres som gyldig hvis den oppfyller ett av følgende vilkår:

  • $s$ er tom.
  • $s_1 = $ (, $s_m = $ ), og $s_{2,3,\ldots,m-1}$ er gyldig.
  • Det finnes en posisjon $k$ ($1 \le k < m$) slik at $s_{1,2,\ldots,k}$ er gyldig og $s_{k+1,k+2,\ldots,m}$ er gyldig.

To posisjoner $i, j$ ($1 \le i < j \le m$) i parentesfølgen $s_{1,2,\ldots,m}$ sies å være matchet hvis og bare hvis både $s_{i,i+1,\ldots,j}$ og $s_{i+1,i+2,\ldots,j-1}$ er gyldige.

Gitt en heltallsfølge med lengde $n$, $a_1, a_2, \ldots, a_n$, der $n$ er garantert å være et partall. Vi konstruerer en ny heltallsfølge $c_1, c_2, \ldots, c_n$ gjennom en gyldig parentesfølge $b_1, b_2, \ldots, b_n$, slik at $\forall 1 \le i \le n, c_i = a_{p_i}$, der $p_i$ er posisjonen som er matchet med posisjon $i$ i $b_{1,2,\ldots,n}$.

Finn en gyldig parentesfølge $b_{1,2,\ldots,n}$ slik at den leksikografiske rekkefølgen til $c_{1,2,\ldots,n}$ minimeres. Hvis det finnes flere løsninger, kan du skrive ut hvilken som helst av dem.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 2.5 \times 10^5$), som angir antall testtilfeller.

For hvert testtilfelle:

Den første linjen inneholder et heltall $n$ ($1 \le n \le 5 \times 10^5$), som angir lengden på følgen $a$, og det er garantert at $n$ er et partall.

Den andre linjen inneholder $n$ mellomromseparerte heltall, som representerer $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).

Det er garantert at summen av $n$ ikke overstiger $5 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut en linje som inneholder en streng med lengde $n$, som representerer $b_{1,2,\ldots,n}$.

Eksempler

Inndata 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

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