Unusual competitions

Interview

Time limit1sMemory limit1024 MB

Summary

Given a bracket string of length up to 10^6, find the minimum total length of subsegment reorders needed to make it correct, or -1 if impossible.

Level: Medium4 of 10
Topics: String, Prefix sum, Greedy
Solved: No attempts yet

Statement

Dmitry's class got a strange assignment from the teacher. Each student had to invent a sequence of any length made only of opening and closing brackets. Then the students took turns reading out their sequences. When Dima's turn came, he noticed that every classmate had a correct bracket sequence, but he did not know whether his own was correct.

Dima thinks he missed the word "right" in the task statement, so he wants to fix his sequence with small changes. He may perform the reorder operation any number of times (possibly zero). A reorder picks any subsegment of the sequence and rearranges its characters in any order. The operation takes $l$ nanoseconds, where $l$ is the length of the chosen subsegment. A reorder never changes the number of opening and closing brackets.

Dima has to answer soon, so he wants to make his sequence correct as fast as possible. Help him, or determine that it is impossible.

Input

The first line contains one integer $n$ ( $1 \le n \le 10^6$ ), the length of Dima's sequence. The second line contains a string of length $n$ made only of ( and ).

Output

Print the minimum number of nanoseconds needed to make the sequence correct, or -1 if it is impossible.

Hint

A bracket sequence is called correct if you can insert "+" and "1" into it to get a well-formed mathematical expression. For example, (())(), (), and (()(())) are correct, while )(, ((), and (()))( are not.

Examples2

Example 1
Input
```
8
))((())(
```
Expected output
```
6
```
Example 2
Input
```
3
(()
```
Expected output
```
-1
```