Universal Cup Judging System

Universal Cup

実行時間制限: 1.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Ciąg nawiasowy to napis złożony ze znaków ( oraz ). Ciąg nawiasowy $s_{1,2,\ldots,m}$ nazywamy poprawnym, jeśli spełnia jeden z poniższych warunków:

  • $s$ jest pusty.
  • $s_1 = $ (, $s_m = $ ) oraz $s_{2,3,\ldots,m-1}$ jest poprawny.
  • Istnieje pozycja $k$ ($1 \le k < m$) taka, że $s_{1,2,\ldots,k}$ jest poprawny oraz $s_{k+1,k+2,\ldots,m}$ jest poprawny.

Mówimy, że dwie pozycje $i, j$ ($1 \le i < j \le m$) w ciągu nawiasowym $s_{1,2,\ldots,m}$ są dopasowane wtedy i tylko wtedy, gdy zarówno $s_{i,i+1,\ldots,j}$, jak i $s_{i+1,i+2,\ldots,j-1}$ są poprawne.

Dany jest ciąg liczb całkowitych o długości $n$: $a_1, a_2, \ldots, a_n$, gdzie $n$ jest gwarantowanie parzyste. Konstruujemy nowy ciąg liczb całkowitych $c_1, c_2, \ldots, c_n$ za pomocą poprawnego ciągu nawiasowego $b_1, b_2, \ldots, b_n$ w taki sposób, że $\forall 1 \le i \le n, c_i = a_{p_i}$, gdzie $p_i$ jest pozycją dopasowaną do pozycji $i$ w $b_{1,2,\ldots,n}$.

Znajdź poprawny ciąg nawiasowy $b_{1,2,\ldots,n}$, dla którego porządek leksykograficzny ciągu $c_{1,2,\ldots,n}$ jest najmniejszy. Jeśli istnieje wiele rozwiązań, wypisz dowolne z nich.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 2.5 \times 10^5$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego:

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 5 \times 10^5$), oznaczającą długość ciągu $a$; gwarantowane jest, że $n$ jest parzyste.

Drugi wiersz zawiera $n$ oddzielonych spacjami liczb całkowitych, oznaczających $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).

Gwarantowane jest, że suma $n$ nie przekracza $5 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz wiersz zawierający napis o długości $n$, oznaczający $b_{1,2,\ldots,n}$.

Przykład

Wejście 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

Wyjście 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.