题目描述

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 $ 的括号序列，如果有多种解，输出任意一种即可。

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

样例

input

6
2 3 6 1 4 5

output

()()()

数据范围与提示

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

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