该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile6043.zip](file://AdditionalFile6043.zip?type=additional_file)

#6043. 「雅礼集训 2017 Day7」蛐蛐国的修墙方案

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

Do you wanna build a wall?

在离跳蚤国很远的地方有一个蛐蛐国，最近蛐蛐国选出了一位新的领导人。

这位领导人上任之后做的第一件事，就是在蛐蛐国和它的一个邻国 —— 蝈蝈国之间修一堵围墙。

围墙可以看成是一个长度为 $n$ 的括号序列，与此同时还有一个长度为 $n$ 的排列 $P$，一个围墙被称为稳的，当且仅当：

1. 这个括号序列是合法的；
2. 构造一张 $n$ 个点的图，当且仅当第 $i$ 个位置是左括号时，点 $i$ 向点 $P_i$ 连边，最后形成的图必须满足每个点的度数均为一。

保证对于任意 $i$ 有 $i \neq P_i$。

一个括号序列合法的定义如下：

1. 空序列是合法的；
2. 如果 $A$ 是合法的，那么 $\texttt{(}A\texttt{)}$ 也是合法的；
3. 如果 $A$ 和 $B$ 都是合法的，那么 $AB$ 也是合法的。

例如 $\texttt{()()((()()))}$ 是合法的，而 $\texttt{())(()}$ 不是。

现在蛐蛐国的领导人想知道一种合法的修墙方案。

输入格式

第一行一个整数 $n$，表示括号序列的长度。

接下来一行 $n$ 个正整数表示排列 $P_i$。

输出格式

输出一行一个长度为 $n$ 的括号序列，如果有多种解，输出任意一种即可。

注意，样例输出只是一种参考解，解可能并不唯一。

样例

输入

6
2 3 6 1 4 5

输出

()()()

数据范围与提示

本题有三个子任务，只有通过一个子任务中的全部测试点才能获得该子任务的所有分数。

子任务 1：$n = 20$，10 分；
子任务 2：$n = 40$，30 分；
子任务 3：$n = 100$，60 分。