CF1685C Bring Balance

Alina 有一个长度为 $2n$ 的括号序列 $s$，由 $n$ 个左括号 `(` 和 $n$ 个右括号 `)` 组成。她想把这个括号序列变成一个平衡括号序列。 平衡括号序列定义为：能通过插入字符 `+` 和 `1` 使之成为合法数学表达式的序列。例如，序列 `(())()`、`()` 和 `(()(()))` 是平衡的，而 `)(`、`(()` 和 `(()))(` 就不是的。 在一次操作中，她可以反转 $s$ 的任意子串。 请求出最少几次操作可将 $s$ 转换为平衡括号序列。可以证明，这总是能在 $n$ 次操作中完成。

无

无

在第一组数据中，字符串已经平衡。 在第二组数据中，字符串转换如下：`())((()))(`$\to$`()()(()))(`$\to$`()()(())()`，最后一个字符串是平衡的。 在第三组数据中，字符串最终将被转换为 `((()))((()))`。