被普及但是国家集训队选手都不会的题暴打了。

题意

给定长度为 的排列 ，要求构造合法括号序列 使得 同样合法。

思路

构造要满足两个同时合法，感觉非常困难，不妨考虑强制使得其中一个合法然后让另一个 自求多福 尽可能最优。

不妨从前往后构造，因为我们要给构造另一个序列尽可能多的自由度，所以试着往一个前缀里加东西。如果这样，要很好地使第一个序列合法，我们的修改就得是右括号变成左括号。

首先令 ，然后考虑 我们可以随意替换其中一个变成左括号。这样每次我们加入两个右括号，然后再替换出一个左括号，显然我们第一个序列就合法了。

然后第二个序列想要构造得比较好，那么就得把左括号尽可能地往左放，于是我们维护一个堆存所有的右括号的 ，然后选一个最小的替换成左括号，这样就可以得到一个尽可能优的第二个序列了。

什么，你要我证明这个东西足够优？对不起，咕咕咕。

最后判无解并输出。

CODE

#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1000010,FSIZE=1<<26;
int n,a[N],sum;
bool ans[N];
priority_queue<int> h;
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;*InF<33;++InF);
    for(x=0;*InF>32;x=x*10+(*InF++^48));
}
void no(){printf("NIE");exit(0);}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);
    for(int i=1;i<=n;++i) read(a[i]);
    h.push(-a[1]);
    for(int i=1;i<=n;){
        ans[-h.top()]=1;
        h.pop();
        h.push(-a[++i]);
        h.push(-a[++i]);
    }
    for(int i=1;i<=n;++i)
        if((sum+=ans[i]*2-1)<0) no();
    if(sum) no();
    for(int i=1;i<=n;++i) putchar(ans[i]?'(':')');
    return(0);
}