Unusual Competitions
Contest: Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 1300
Tags: greedy

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.

Input format:
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.

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

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
8
))((())(

Example output:
6

Example input:
3
(()

Example output:
-1

Editorial:
Obviously, if the number of opening brackets is not equal to the number of closing ones, then since the described operation does not change their number, it will be impossible to get the correct sequence. Otherwise, if their numbers are equal, you can take the entire string and rearrange its $$$n$$$ characters so that the string becomes a right bracketed sequence, for example, "(((($$$\dots$$$))))".
Let $$$p_i$$$ be a prefix balance on the first $$$i$$$ characters, that is, the difference between the number of opening and closing brackets.
Consider an index $$$i$$$ such that $$$bal_{i-1} \leq 0$$$, $$$bal_{i} < 0$$$, or $$$bal_{i-1} < 0$$$, $$$bal_i \leq 0$$$. Then, if the $$$s_i$$$ character does not participate in any shuffle oeration, the resulting string will have a $$$i$$$th or $$$i-1$$$th prefix balance negative, making the resulting sequence incorrect. This means that at least characters with such indexes $$$i$$$ must participate in at least one operation. It will be shown below how to use only them in shuffles to make a right bracketed sequence.
Let's represent this bracketed sequence as a polyline. It will start at the point with coordinates $$$(0,0)$$$, end at the point with coordinates $$$(2n, 0)$$$, $$$i$$$ - th vector of this polyline will be equal to $$$(+1, +1)$$$, if $$$s_i = $$$ ( and $$$(+1, -1)$$$ otherwise. Then the above-described indexes $$$i$$$, which must participate in at least one operation — are exactly all the segments below the line $$$x=0$$$. To make the sequence correct, we will turn all consecutive segments of such brackets backwards. It's not hard to see that the sequence will become correct.
An example of this conversion is shown below: