题目描述

题目译自 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$ 个字符组成的字符串，每个字符是 ( 或 )，表示在每张卡牌上应画的括号。如果存在多种正确答案，你的程序可以输出其中任意一种。

6
4 6 1 2 3 5

(()())

2
2 1

NIE

样例 3

见附加文件下 [naw1.in](file:naw1.in) 和 [naw1.out](file:naw1.out)。

该样例满足 $n=2000, p_{i}=2i-1, p_{n/2+i}=2i$ 对于 $1 \leq i \leq n/2$，答案是 ()()...()；

样例 4

见附加文件下 [naw2.in](file:naw2.in) 和 [naw2.out](file:naw2.out)。

该样例满足 $n=2000, p_{2i-1}=i, p_{2i}=n/2+i$ 对于 $1 \leq i \leq n/2$，答案是 ((...()))...)；

样例 5

见附加文件下 [naw3.in](file:naw3.in) 和 [naw3.out](file:naw3.out)。

该样例满足 $n=1000000, p_{i}=n+1-i$ 对于 $1 \leq i \leq n$，答案是 NIE；

样例 6

见附加文件下 [naw4.in](file:naw4.in) 和 [naw4.out](file: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$