P8355 "WHOI-1" ymh Is Brother AK!!!

$2077$ 年春。$15$ 岁的 miku 正在对着你谷发呆，突然看到一个奇怪的问题，你能帮帮他么？？ ---- 你要先学会一些定义。 我们约定一个字符串下标从 $1$ 开始，$s[l,r]$ 表示 $s_ls_{l+1}\dots s_r$ 拼接成的一个字符串。 --- 定义括号匹配串如下： - 空串是括号匹配串。 - 如果 $A$ 是括号匹配串，则 $(A)$ 是括号匹配串。 - 如果 $A,B$ 是括号匹配串，则 $AB$ 是括号匹配串。 --- 括号匹配前缀长度是指最大的 $k$ 使得 $s[1,k]$ 是一个括号匹配串。 比如： - $s=\text{(())(()}$ 时括号匹配前缀长度是 $4$。 - $s=\text{()()()(()))(}$ 时括号匹配前缀长度是 $10$。

给你一个括号串 $s$。定义一次操作是交换他们当中相邻的两个字符。 你的任务是找出若干次操作后 $s$ 的括号匹配前缀长度最大值。

The first line contains a positive integer $n$, the length of the string. The next line contains a string $s$.

Output one non-negative integer, the answer.

This problem uses $\texttt{Subtask}$ scoring. You can get the score of a $\texttt{Subtask}$ only if you pass all test points in that $\texttt{Subtask}$. | $\texttt{Subtask}$ ID | Special Restrictions | Score | | :----------: | :----------: | :----------: | | 1 | Contains only left parentheses or only right parentheses | 2 | | 2 | $n \leq 2$ | 3 | | 3 | $n \leq 10$ | 10 | | 4 | $n \leq 1000$ | 20 | | 5 | None | 65 | For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^6$. Translated by ChatGPT 5