题目描述

题目译自 XXVIII Olimpiada Informatyczna – III etap Nawiasowania

Bajtazar 正在设计一个新的纸牌魔术。他有一副由 $n$ 张卡牌组成的牌堆，卡牌编号从 $1$ 到 $n$。他计划在每张卡牌上画上一个开括号 ( 或闭括号 )，使得这些卡牌按顺序排列时，能形成一个合法的括号序列。

Bajtazar 洗牌的技术非常娴熟，每次洗牌的结果都一样：洗牌后，第 $i$ 个位置上的卡牌编号是 $p_i$。他的魔术目标是，在洗牌后，卡牌仍然能形成一个合法的括号序列。

例如，对于 $n=6$ 张卡牌，洗牌后的排列为 $p=4,6,1,2,3,5$，可以在卡牌上画括号，使得洗牌前卡牌形成括号序列 (())()，洗牌后形成括号序列 ()()()。

请你帮助 Bajtazar，编写一个程序，判断给定的排列 $p$ 是否能实现这个魔术。如果可以，还要找出一种合法的括号画法。

---

输入格式

输入的第一行包含一个偶数 $n$ $(2 \leq n \leq 1000000)$，表示卡牌数量。
第二行包含一个排列 $p_1, p_2, \ldots, p_n$，由 $1$ 到 $n$ 的数字组成。

---

输出格式

如果无法在卡牌上画出括号，使得洗牌前后都满足合法括号序列的要求，你的程序应输出 NIE。
否则，输出一个由 $n$ 个字符组成的字符串，每个字符是 ( 或 )，表示在每张卡牌上应画的括号。如果存在多种正确答案，你的程序可以输出其中任意一种。

---

样例 1

输入

6
4 6 1 2 3 5

输出

(()())

---

样例 2

输入

2
2 1

输出

NIE

---

样例 3

见附加文件下 naw1.in 和 naw1.out。
该样例满足 $n=2000$, $p_i=2i-1$, $p_{n/2+i}=2i$ 对于 $1 \leq i \leq n/2$，答案是 ()()...()。

---

样例 4

见附加文件下 naw2.in 和 naw2.out。
该样例满足 $n=2000$, $p_{2i-1}=i$, $p_{2i}=n/2+i$ 对于 $1 \leq i \leq n/2$，答案是 ((...()))...)。

---

样例 5

见附加文件下 naw3.in 和 naw3.out。
该样例满足 $n=1000000$, $p_i=n+1-i$ 对于 $1 \leq i \leq n$，答案是 NIE。

---

样例 6

见附加文件下 naw4.in 和 naw4.out。
该样例满足 $n=1000000$, $p_1=1$, $p_n=n$, $p_i=n+1-i$ 对于 $1<i<n$，答案是 ()()...()。

---

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
1	$n \leq 20$	10
2	$n \leq 2000$	30
3	$p_1=1$, $p_n=n$	35
4	无附加限制	25