Parentheses

Time limit4sMemory limit1024 MB

Summary

Given a permutation p of n cards, assign each card an opening or closing bracket so both the original and shuffled orders are correct bracket sequences.

Level: Hard8 of 10
Topics: Graph, Greedy, Implementation
Solved: No attempts yet

Statement

Bajtazar is developing a new card trick. He has a deck of $n$ cards numbered from 1 to $n$ . On each card he wants to draw either an opening or a closing bracket, so that laying the cards out in order forms a correct bracket sequence.

Bajtazar is very good at shuffling, and every shuffle gives the same result: after shuffling, the card in position $i$ is card $p_i$ . The trick requires that after shuffling, the cards still form a correct bracket sequence.

For example, with $n = 6$ and the permutation $p = 4, 6, 1, 2, 3, 5$ , the brackets can be drawn so that before shuffling the cards form (()()), and after shuffling they form ()(()).

Input

The first line contains an even integer $n$ ( $2 \le n \le 1\,000\,000$ ), the number of cards. The second line contains the permutation $p_1, p_2, \ldots, p_n$ of the numbers from 1 to $n$ .

Output

Print the word NIE if the brackets cannot be drawn so that the cards meet the requirements. Otherwise, print a word of $n$ characters, each ( or ), giving the bracket to draw on each card in order. If more than one correct answer exists, print any of them.

Examples2

Example 1
Input
```
6
4 6 1 2 3 5
```
Expected output
```
(()())
```
Example 2
Input
```
2
2 1
```
Expected output
```
NIE
```