P9406 [POI 2020/2021 R3] 嵌套 / Nawiasowania
题目背景
译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Nawiasowania](https://szkopul.edu.pl/problemset/problem/YmEnXY44jxuLdZPFrhWOfOQi/statement/)。
d2t2。
题目描述
有 $n$ 张卡片，每张上写了一个左括号或右括号。
按 $1\sim n$ 的顺序排列这些卡片，得到的括号序列是合法的。
给你一个长度为 $n$ 的排列 $p$。
按 $p$ 所示次序排列这些卡片，即新第 $i$ 张放原第 $p_i$ 张，得到的括号序列也是合法的。
构造符合要求的括号序列，按 $1\sim n$ 的顺序输出。
如果有多解，任意一种都行。无解输出 `NIE`。
输入格式
第一行一个整数 $n$。
第二行 $n$ 个整数表示排列 $p$。
输出格式
如果有解，输出一行 $n$ 个字符，左括号或右括号。
如果无解，输出 `NIE`。
说明/提示
样例解释：
对于所有数据，$2\leq n\leq 1000000$。
| 子任务编号 | 附加限制 | 分数 |
| :----------: | :----------: | :----------: |
| 1 | $n\leq 20$ | 10 |
| 2 | $n\leq 2000$ | 30 |
| 3 | $p_1=1,p_n=n$ | 35 |
| 4 | | 25 |