Valid Bracket Sequence Permutation

You are given an even integer \(n\) and a permutation \(p = [p_1, p_2, \ldots, p_n]\) of \([1, n]\). There are \(n\) cards, each inscribed with either a left bracket \( ( \) or a right bracket \( ) \). When the cards are arranged in natural order from position \(1\) to \(n\) (i.e. the sequence \(S = S_1S_2\ldots S_n\)), the bracket sequence is valid. Moreover, if you rearrange the cards according to the permutation \(p\) — that is, the new sequence \(T\) is defined by \(T_i = S_{p_i}\) for \(1 \le i \le n\) — then \(T\) is also a valid bracket sequence.

Your task is to construct and output a valid bracket sequence \(S\) (of length \(n\)) satisfying the above condition, or output NIE if no solution exists.

A bracket sequence is valid if and only if:

• It contains exactly \(\frac{n}{2}\) left brackets and \(\frac{n}{2}\) right brackets.
• For every prefix of the sequence, the number of left brackets is at least the number of right brackets.

Hint: Let \(r\) be the inverse permutation of \(p\), i.e. \(r[i]\) is the new position of the card originally at position \(i\) (so that \(p_{r[i]} = i\)). A natural construction is to set

[ S_i = \begin{cases} (, & \text{if } r[i] \le \frac{n}{2}, \ ), & \text{otherwise.} \end{cases} ]

This ensures that in the permuted order \(T\) the first half are left brackets and the remaining are right brackets (which is valid), while \(S\) is valid provided that for every prefix \(1 \le k \le n\),

[ 2\cdot#{i \le k : r[i] \le \frac{n}{2}} \ge k. ]

If this condition fails for any prefix, then output NIE.

inputFormat

The first line contains an even integer \(n\) (\(2 \le n \le 10^5\)).

The second line contains \(n\) space-separated integers \(p_1, p_2, \ldots, p_n\) representing a permutation of \([1, n]\).

outputFormat

Output a valid bracket sequence \(S\) of length \(n\) that satisfies the conditions described above. If no such sequence exists, output NIE.

sample

6
1 3 2 4 6 5

((()))