Bajtazar 正在开发一个新的纸牌魔术。他有一副 $n$ 张牌，编号从 $1$ 到 $n$。他想在每张牌上画一个左括号或右括号，使得当他按顺序排列这些牌时，它们构成一个合法的括号序列。

Bajtazar 非常擅长洗牌，每次洗牌的结果都是固定的：洗牌后，第 $i$ 个位置上的牌是编号为 $p_i$ 的牌。这个魔术的目的是让这些牌在洗牌后依然构成一个合法的括号序列。

例如，对于 $n = 6$ 张牌和排列 $p = 4, 6, 1, 2, 3, 5$，我们可以这样画括号：使得洗牌前这些牌构成括号序列 (()())，而洗牌后构成括号序列 ()(())：

请帮助 Bajtazar 编写一个程序，对于给定的排列 $p$，判断是否可以完成这个魔术，如果可以，请找出一种合法的括号绘制方案。

输入格式

第一行包含一个偶数 $n$ ($2 \le n \le 1\,000\,000$)，表示牌的数量。第二行包含一个排列 $p_1, p_2, \dots, p_n$，表示从 $1$ 到 $n$ 的数字。

输出格式

如果无法按照要求在牌上绘制括号，你的程序应输出一个单词 NIE。否则，输出一个由 $n$ 个字符 ( 和 ) 组成的字符串，表示应在对应的牌上绘制的括号。如果存在多个合法的答案，输出其中任意一个即可。

样例

输入格式 1

6
4 6 1 2 3 5

输出格式 1

(()())

输入格式 2

2
2 1

输出格式 2

NIE