一个显然的思路是：在排列 \(p\) 的括号串合法的基础上，使得左括号在原括号串中尽量靠左，这样答案更有可能合法。于是我们求出这个原括号尽量靠左的括号串（下文称为“最优括号串”），然后 check 合法性即可。
下文中 \(s\) 是排列 \(p\) 的括号串。
当 \(n=2\) 时，唯一的填法是令 \(s_1\gets\texttt{(},s_2\gets\texttt{)}\)，这个填法显然是最优括号串。
如果我们找出了 \(n=n_0-2\) 的最优括号串，考虑如何找出 \(n=n_0\) 的最优括号串。显然已经填好的左括号是不能动的，因为 \(n=n_0-2\) 时已经是最优括号串，任何移动都会导致括号串不合法。我们先令多出的两位 \(s_{n_0-1}\gets\texttt{)},s_{n_0}\gets\texttt{)}\)，只需要在这个括号串中改一个左括号为右括号，且括号串依然合法即可。
注意到除了 \(s_{n_0}\) 处的右括号，其他的右括号都可以改为左括号。这个性质可以通过 \(n=n_0-2\) 时的最优括号串性质易证。
于是我们用小根堆维护当前所有可以改为左括号的右括号的位置，进行增量构造。小根堆中初始有 \(p_1\)，进行 \(\frac{n}{2}\) 次操作，每次取出小根堆堆顶并对应位置置为左括号，然后将新产生的可改动位置压入堆中即可。
最后 check 答案字符串的合法性并输出。
时间复杂度 \(O(n\log n)\)。
// Problem: P9406 [POI2020-2021R3] Nawiasowania
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9406
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
#define likely(exp) __builtin_expect(!!(exp), 1)
#define unlikely(exp) __builtin_expect(!!(exp), 0)
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const int N = 1e6+5;
int n, a[N];
char s[N];
priority_queue<int, vector<int>, greater<int>> heap;
int main() {
scanf("%d", &n);
rep(i, 1, n) {
scanf("%d", &a[i]);
s[i] = ')';
}
s[n+1] = 0;
heap.push(a[1]);
rep(i, 1, n/2) {
s[heap.top()] = '(';
heap.pop();
if(i < n / 2) {
heap.push(a[2*i]);
heap.push(a[2*i+1]);
}
}
int now = 0;
rep(i, 1, n) {
if(s[i] == '(') ++now;
else --now;
if(now < 0) return puts("NIE")&0;
}
puts(s+1);
return 0;
}