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

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

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 分。