You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

本题有部分分。

在时光的流转中，偶然的相遇如同盛开的花朵，绽放于繁华与静谧之间。阳光或细雨，两个灵魂在瞬间交汇，命运的丝线悄然编织。

“有缘千里来相会”，道出了人心的奥秘。每段缘分，都是星辰的眷顾，穿越千山万水，将彼此相连。在这个瞬息万变的时代，人与人之间的情感愈显珍贵，仿佛生命中之光，照亮心灵深处。

每一次邂逅，都是宇宙谱写的诗篇，静待吟诵。

特别地，如果你构造的解不满足字典序最小，但也是合法括号串，你可以获得这个测试点 $50\%$ 的分数。

题目描述

缘分化成了一个长度为 $2n$ 的合法括号串，这 $2n$ 个字符（( 或 )）代表了 $2n$ 个灵魂，分成 $n$ 组命运，每组恰好包含 $2$ 个灵魂。

对于每组灵魂，由于它们相互连接，所以它们代表的字符需要相同。

现在，给定这 $2n$ 个灵魂所在的命运组，求是否存在这样的合法括号串，如果存在，则构造一组字典序最小的解，否则输出 :( 表示不存在。

输入格式

第一行，一个正整数 $n$。

第二行，$2n$ 个正整数 $p_i$ 表示第 $i$ 个灵魂所在的命运组，保证 $1,2,3,\cdots,n$ 恰好都在 $p$ 中出现 $2$ 次。

输出格式

如果存在，则构造字典序最小的解，否则输出 :( 表示不存在。

样例 #1

样例输入 #1

4
1 1 3 2 2 4 4 3

样例输出 #1

(()(()))

样例 #2

样例输入 #2

见下发文件 fate2.in。

fate2.in

样例输出 #2

见下发文件 fate2.ans。

fate2.ans

样例 #3

样例输入 #3

见下发文件 fate3.in。

fate3.in

样例输出 #3

见下发文件 fate3.ans。

fate3.ans

样例 #4

样例输入 #4

见下发文件 fate4.in。

fate4.in

样例输出 #4

见下发文件 fate4.ans。

fate4.ans

提示

对于所有数据保证：$1\le n\le 10^6$，$1,2,3,\cdots,n$ 恰好都在 $p$ 中出现 $2$ 次。

• 特殊性质 A：对于 $\forall i\in[1,2n]$，$p_i=\lceil\frac{i}{2}\rceil$；
• 特殊性质 B：对于 $\forall i\in[1,2n]$，$p_i=p_{2n-i+1}$；
• 特殊性质 C：对于 $\forall i\in[1,n]$，$p_i=p_{i+n}$。