괄호 배치

바자타르는 새로운 카드 마술을 만들고 있다. 그에게는 1부터 $n$까지 번호가 붙은 카드 $n$장이 있다. 각 카드에 여는 괄호 또는 닫는 괄호를 그려서, 카드를 순서대로 늘어놓았을 때 올바른 괄호 문자열이 되도록 하려 한다.

바자타르는 카드를 섞는 데 아주 능숙해서, 섞을 때마다 결과가 항상 같다. 섞은 뒤 $i$번째 자리에는 번호 $p_i$인 카드가 놓인다. 이 마술은 카드를 섞은 뒤에도 카드가 여전히 올바른 괄호 문자열을 이루어야 한다.

예를 들어 $n = 6$이고 순열이 $p = 4, 6, 1, 2, 3, 5$일 때, 섞기 전에는 카드가 (()())를 이루고 섞은 뒤에는 ()(())를 이루도록 괄호를 그릴 수 있다.

첫 줄에 카드의 개수인 짝수 정수 $n$ ($2 \le n \le 1\,000\,000$)이 주어진다. 둘째 줄에는 1부터 $n$까지의 수로 이루어진 순열 $p_1, p_2, \ldots, p_n$이 주어진다.

카드에 괄호를 그려서 조건을 만족시킬 수 없으면 NIE라는 단어를 출력한다. 그렇지 않으면 각 카드에 그릴 괄호를 순서대로 적은, $n$개의 (와 ) 문자로 이루어진 단어를 출력한다. 올바른 답이 여러 개이면 그중 아무것이나 출력해도 된다.