题目描述

题目译自 Open Olympiad in Informatics 2020 Day1 T2 「Интересные конкурсы / Unusual competitions」。

老师给迪米特里所在的班级布置了一项非常奇怪的任务——她要求每个学生设计一个任意长度的序列，仅由开括号和闭括号组成。之后，学生们依次报出他们设计的序列。轮到迪米特里时，他突然意识到，所有同学设计的都是合法的括号序列，而他不确定自己设计的序列是否合法。

迪米特里怀疑自己可能错过了题目中提到的合法这个词，因此他想紧急补救——为此，他决定对自己的序列做一些修改。具体来说，他可以进行任意次数（包括零次）打乱操作。在一次打乱操作中，迪米特里选择序列的一个任意子段，并以任意方式重新排列该子段内的所有字符。这样的操作耗时正好为 $l$ 纳秒，其中 $l$ 是所选子段的长度。显然，这种操作不会改变开括号和闭括号的数量。

迪米特里的轮次即将到来，因此他向你求助。帮助他计算将序列变成合法括号序列所需的最小时间，或者判断是否无法通过打乱操作实现这一目标。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 10^{6})$，表示迪米特里序列的长度。

第二行包含一个长度为 $n$ 的字符串，仅由字符 ( 和 ) 组成。

输出格式

输出一个数字，即将序列变成合法括号序列所需的最小纳秒数；如果无法通过打乱操作实现，则输出 -1。

8
))((())(

6

我们提醒，括号序列被称为合法的，如果通过在其中插入字符 + 和 1，可以将其变成一个合法的数学表达式。例如，序列 (()())、() 和 (()(())) 是合法的，而 )(、(() 和 (()))( 则不是。

在第一个示例中，可以先打乱从第一个到第四个字符的子段，将其替换为 ()()，得到序列 ()()())(；然后打乱从第七个到第八个字符的子段，将其替换为 ()，最终得到合法的括号序列 ()()()()。这些操作总共耗时 $4 + 2 = 6$ 纳秒。

3
(()

-1

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。