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 parenthesis in such a way that when he lays these cards out in order, they form a valid parenthesis sequence.

Bajtazar is very skilled at shuffling cards, and every time he performs the shuffle, it results in the same outcome: after shuffling, the card at the $i$-th position is the card with the number $p_i$. The trick is intended to ensure that after the cards are shuffled, they still form a valid parenthesis sequence.

For example, for $n = 6$ cards and the permutation $p = 4, 6, 1, 2, 3, 5$, we can draw the parentheses such that before shuffling, the cards form the sequence (()()), and after shuffling, they form the sequence ()(()):

Help Bajtazar and write a program that, for a given permutation $p$, determines whether it is possible to perform the trick, and if so, finds a valid way to draw the parentheses.

Input

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

Output

Your program should output the single word NIE if it is impossible to draw parentheses on the cards to satisfy the problem requirements. Otherwise, you should output a string of $n$ characters, consisting of ( and ), representing the parentheses to be drawn on the cards in order. If there is more than one valid answer, your program may output any of them.

Examples

Input 1

6
4 6 1 2 3 5

Output 1

(()())

Input 2

2
2 1

Output 2

NIE

Evaluation tests

1. $n = 2000$, $p_i = 2i - 1$, $p_{n/2+i} = 2i$ for $1 \le i \le n/2$; answer ()() ··· ();
2. $n = 2000$, $p_{2i-1} = i$, $p_{2i} = n/2 + i$ for $1 \le i \le n/2$; answer (( ··· ()) ··· );
3. $n = 1\,000\,000$, $p_i = n + 1 - i$ for $1 \le i \le n$; answer NIE;
4. $n = 1\,000\,000$, $p_1 = 1$, $p_n = n$; $p_i = n + 1 - i$ for $1 < i < n$; answer ()() ··· ().

Subtasks