前缀和一下,从前缀和为 $0$ 的位置将序列分成若干段。
对于每一段,如果它是负的,则这一段必须要重排,否则不用。
```cpp
const int N = 1e6 + 7;
int n, c[2], a[N], ans;
char s[N];
int main() {
rd(n), rds(s, n);
for (int i = 1; i <= n; i++)
if (s[i] == '(') c[0]++;
else c[1]++;
if (c[0] != c[1]) return print(-1), 0;
for (int i = 1, p = 0; i <= n; i++) {
if (s[i] == '(') a[i] = a[i-1] + 1;
else a[i] = a[i-1] - 1;
if (!a[i]) {
bool ok = 0;
for (int j = p + 1; j <= i; j++)
if (a[j] < 0) ok = 1;
if (ok) ans += i - p;
p = i;
}
}
print(ans);
return 0;
}
```