CF1322A Unusual Competitions

一个括号序列被称为正确（规范）的，如果通过在其中插入“+”和“1”可以得到一个格式正确的数学表达式。例如，序列“(())()”、“()”和“(()(()))”是正确的，而“) (”、“(()”和“(())) (”是不正确的。 老师给了 Dmitry 的班级一个非常奇怪的任务——她要求每个学生想出一个只包含左括号和右括号的任意长度的序列。之后，所有学生轮流说出他们想出的序列。当轮到 Dima 时，他突然意识到所有同学得到的都是正确的括号序列，而他自己是否得到正确的括号序列却不知道。 Dima 现在怀疑自己只是漏听了题目中的“正确”这个词，所以他现在想通过稍微修改自己的序列来挽救局面。更准确地说，他可以任意多次（也可以不操作）执行重排操作。 重排操作是指选择序列中的任意连续子段（子串），然后以任意方式重新排列该子段中的所有字符。这样的操作需要 $l$ 纳秒，其中 $l$ 是被重排的子段长度。显然，重排操作不会改变左括号和右括号的数量。例如，对于“))(("，他可以选择子串“) (”并重排为“)()(”，该操作耗时 $2$ 纳秒。 由于 Dima 很快就要回答了，他希望以最快的速度将自己的序列变为正确的括号序列。请你帮助他完成这个目标，或者判断这是否不可能。

第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示 Dima 的序列长度。 第二行包含一个长度为 $n$ 的字符串，仅由字符“(”和“)”组成。

输出一个整数，表示将序列变为正确括号序列所需的最少纳秒数。如果无法做到，输出“-1”。

在第一个样例中，我们可以首先重排第 1 到第 4 个字符，将其替换为“()()”，整个序列变为“()()())(”。然后重排第 7 到第 8 个字符，将其替换为“()”。最终序列为“()()()()”，总耗时为 $4 + 2 = 6$ 纳秒。 由 ChatGPT 4.1 翻译