CF1970A1.Balanced Shuffle (Easy)

括号序列是仅由字符“(”和“)”组成的字符串，例如“(()((”。

平衡括号序列是指可以通过在其中插入数字和运算符后成为有效数学表达式的括号序列，例如“(()(()))”。

括号序列的平衡度定义为左括号“(”的数量减去右括号“)”的数量。例如，序列“(()((”的平衡度为 $3$。

平衡括号序列也可以定义为平衡度为 $0$，且其每一个前缀的平衡度都不为负数的括号序列。

我们定义“平衡洗牌”操作如下：对于一个括号序列，首先，对于序列中的每一个字符，计算该字符之前的前缀的平衡度，并将其与该字符在原序列中的位置一起记录在表格中。例如：

$$\begin{aligned} \text{前缀平衡度} &\quad 0\ 1\ 2\ 1\ 2\ 3\ 2\ 1 \\ \text{位置} &\quad 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8 \\ \text{字符} &\quad ( ( ) ( ( ) ) ) \end{aligned}$$

然后，将表格的列按照前缀平衡度升序排序，若平衡度相同，则按位置降序排序。在上述例子中，排序后得到：

$$\begin{aligned} \text{前缀平衡度} &\quad 0\ 1\ 1\ 1\ 2\ 2\ 2\ 3 \\ \text{位置} &\quad 8\ 7\ 4\ 1\ 5\ 3\ 2\ 6 \\ \text{字符} &\quad ) ) ( ( ( ) ( ) \end{aligned}$$

表格最后一行的字符依次组成新的括号序列，在本例中为“()(()())”。这个序列称为对原序列应用平衡洗牌操作的结果，简称为该序列的平衡洗牌。

给定一个平衡括号序列，请输出它的平衡洗牌。

输入仅一行，包含一个只由“(”和“)”组成的字符串 $s$。保证该字符串是非空的平衡括号序列，且长度不超过 $500\,000$。

输出括号序列 $t$，即 $s$ 的平衡洗牌。

由 ChatGPT 4.1 翻译