P9406 [POI 2020/2021 R3] Nesting / Nawiasowania

Translated from [XXVIII Olimpiada Informatyczna - Stage III](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Nawiasowania](https://szkopul.edu.pl/problemset/problem/YmEnXY44jxuLdZPFrhWOfOQi/statement/). d2t2。

There are $n$ cards, each with either a left parenthesis or a right parenthesis written on it. Arrange these cards in the order $1 \sim n$, and the resulting parentheses sequence is valid. You are given a permutation $p$ of length $n$. Arrange these cards in the order specified by $p$, i.e., the new $i$-th card is the original $p_i$-th card, and the resulting parentheses sequence is also valid. Construct a parentheses sequence that satisfies the requirements, and output it in the order $1 \sim n$. If there are multiple solutions, any one is acceptable. If there is no solution, output `NIE`.

The first line contains an integer $n$. The second line contains $n$ integers denoting the permutation $p$.

If there is a solution, output one line with $n$ characters, each being a left parenthesis or a right parenthesis. If there is no solution, output `NIE`.

Sample explanation:  Constraints: for all testdata, $2\leq n\leq 1000000$. | Subtask ID | Additional Constraints | Score | | :----------: | :----------: | :----------: | | 1 | $n\leq 20$ | 10 | | 2 | $n\leq 2000$ | 30 | | 3 | $p_1=1,p_n=n$ | 35 | | 4 | | 25 | Translated by ChatGPT 5