Logo Quest Online Judge

QOJ

时间限制:2 s 空间限制:1024 MB
统计

题目描述

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

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

样例

样例输入 1

6
2 3 6 1 4 5

样例输出 1

()()()

数据范围与提示

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

子任务 1:$ n = 20 $,10 分;
子任务 2:$ n = 40 $,30 分;
子任务 3:$ n = 100 $,60 分。