CF1322A.Unusual Competitions

A bracketed sequence is called correct (regular) if by inserting "+" and "1" you can get a well-formed mathematical expression from it. For example, sequences "(())()", "()" and "(()(()))" are correct, while ")(", "(()" and "(()))(" are not.

The teacher gave Dmitry's class a very strange task — she asked every student to come up with a sequence of arbitrary length, consisting only of opening and closing brackets. After that all the students took turns naming the sequences they had invented. When Dima's turn came, he suddenly realized that all his classmates got the correct bracketed sequence, and whether he got the correct bracketed sequence, he did not know.

Dima suspects now that he simply missed the word "correct" in the task statement, so now he wants to save the situation by modifying his sequence slightly. More precisely, he can the arbitrary number of times (possibly zero) perform the reorder operation.

The reorder operation consists of choosing an arbitrary consecutive subsegment (substring) of the sequence and then reordering all the characters in it in an arbitrary way. Such operation takes $l$ nanoseconds, where $l$ is the length of the subsegment being reordered. It's easy to see that reorder operation doesn't change the number of opening and closing brackets. For example for "))((" he can choose the substring ")(" and do reorder ")()(" (this operation will take $2$ nanoseconds).

Since Dima will soon have to answer, he wants to make his sequence correct as fast as possible. Help him to do this, or determine that it's impossible.

括号序列被称为**正确（合法）**的，当且仅当我们能在其中插入“+”和“1”，从而得到一个语法正确的数学表达式。例如，序列 (())()、() 和 (()(())) 是正确的，而 )(、(() 和 (()))( 则不是。

老师给德米特里所在的班级布置了一项非常奇怪的任务——她要求每位学生各自构造一个任意长度、仅由左括号和右括号组成的序列。随后，所有学生依次报出自己构造的序列。轮到德米特里时，他突然意识到：所有同学报出的都是正确的括号序列，而他自己是否构造出了正确的括号序列，却完全不确定。

德米特里现在怀疑，自己只是在题目描述中漏看了“正确”这个词。因此，他想通过轻微修改自己的序列来挽回局面。更准确地说，他可以**任意多次（包括零次）**执行“重排”操作。

一次“重排”操作定义如下：任选序列的一个连续子段（子串），然后将该子段内的所有字符以任意顺序重新排列。该操作耗时 $l$ 纳秒，其中 $l$ 为所选子段的长度。显然，重排操作不会改变左括号与右括号各自的总数。例如，对字符串 ))((，他可选取子串 )( 并将其重排为 )()(（该操作耗时 $2$ 纳秒）。

由于德米特里很快就要作答，他希望以最短总耗时使自己的序列变为正确的括号序列。请你帮助他实现这一目标，或判断这是不可能的。

The first line contains a single integer $n$ ($1 \le n \le 10^6$) — the length of Dima's sequence.

The second line contains string of length $n$, consisting of characters "(" and ")" only.

第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 表示迪马序列的长度。

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

Print a single integer — the minimum number of nanoseconds to make the sequence correct or "-1" if it is impossible to do so.

输出一个整数——使序列变为正确的所需的最少纳秒数；如果无法实现，则输出“-1”。

In the first example we can firstly reorder the segment from first to the fourth character, replacing it with "()()", the whole sequence will be "()()())(". And then reorder the segment from the seventh to eighth character, replacing it with "()". In the end the sequence will be "()()()()", while the total time spent is $4 + 2 = 6$ nanoseconds.

在第一个例子中，我们首先可以对第 1 到第 4 个字符组成的子段进行重排，将其替换为 "()()"，此时整个序列变为 "()()())("。然后，再对第 7 到第 8 个字符组成的子段进行重排，将其替换为 "()"。最终序列为 "()()()()"，而总耗时为 $4 + 2 = 6$ 纳秒。