----- 문제 -----

Byteasar는 새로운 카드 트릭을 개발하고 있다. 그는 1부터 n까지의 숫자가 적힌 카드 한 벌을 가지고 있다. Byteasar는 카드 셔플에 매우 능숙하며, 다음의 조건을 만족하도록 각 카드에 여는 괄호 또는 닫는 괄호를 그리려고 한다.

1. 처음에 카드가 오름차순으로 정렬되어 있다. 이때 Byteasar가 각 카드에 두 개의 괄호 기호 중 하나를 적는다. 이때 카드에 적힌 괄호 문자열이 올바른 괄호 문자열이 되어야 한다.

2. 카드를 주어진 순서대로 따라 i번째 위치에 숫자 p_{i}가 적힌 카드가 있도록 섞는다. 섞은 후에도 여전히 카드는 올바른 괄호를 형성해야 한다.

예를 들어, n = 6이고 순열 p가 (4, 6, 1, 2, 3, 5)인 경우 카드를 섞기 전에 괄호열 '(()())'을 형성하면, 주어진 순서에 따라 섞은 후에 괄호열 '()(( ))'을 얻고, 두 괄호열 모두 올바른 괄호열이다.

----- 입력 -----

입력의 첫 번째 줄에는 카드 수를 나타내는 짝수 n(2 ≤ n ≤ 1,000,000)이 주어진다. 두 번째 줄에는 1, 2, ..., n의 순열 p_{1}, p_{2}, . . . , p_{n}가 주어진다. 즉, 1 ≤ i ≤ n에 대하여, p_{i}는 1 이상 n 이하의 정수이며 중복되지 않는다.

----- 출력 -----

요구 사항을 충족하도록 카드에 괄호를 그릴 수 없는 경우 "NIE"를 출력한다. 그렇지 않으면, 섞기 전에 카드에 그려질 괄호열을 출력한다. 만약 가능한 괄호열이 여러 개 있을 경우 그들 중 아무거나 출력해도 좋다.