CF524F And Yet Another Bracket Sequence

Polycarpus 有一个只包含左括号和右括号的有限序列。为了在讲座上不犯困，Polycarpus 通过操作这个括号序列来娱乐自己。他可以进行以下两种操作： - 在序列的任意位置添加任意一个括号（可以在开头、末尾或任意两个已有括号之间插入）； - 循环移动——将序列末尾的最后一个括号移动到序列的开头。 Polycarpus 可以以任意顺序、任意次数地进行上述两种操作。最终，他希望得到一个长度最短的合法括号序列。如果存在多个这样的序列，Polycarpus 希望得到字典序最小的那个。请帮助他找出满足条件的序列。 一个合法括号序列是指可以通过在括号之间插入字符 $1$ 和 $+$ 获得一个合法的算术表达式。每一个左括号都必须有唯一匹配的右括号。例如，序列 “(())()”、"()"、"(()(()))" 都是合法的，而 ")(", "(()" 和 "(()))(" 都不是。 序列 $a_1 a_2\ldots a_n$ 在字典序上小于序列 $b_1 b_2\ldots b_n$，当存在某个 $i$ 满足 $1\leq k

第一行包含 Polycarpus 的括号序列，只由字符 "(" 和 ")" 组成。该序列长度 $1 \leq n \leq 1000000$。

输出经过操作后获得的，长度最短且字典序最小的合法括号序列。

第一个样例的序列已经合法，但为了获得字典序最小的答案，需要进行四次循环移动操作。第二个样例需要在第二和第三个括号之间添加一个右括号，并进行一次循环移动。你也可以先循环移动，再在末尾添加括号。 由 ChatGPT 5 翻译