이상한 대회

디미트리의 반은 선생님에게서 이상한 과제를 받았다. 각 학생은 여는 괄호와 닫는 괄호로만 이루어진 임의의 길이의 수열을 만들어야 했다. 그 뒤 학생들은 차례로 자신이 만든 수열을 발표했다. 디마의 차례가 되었을 때 그는 반 친구들이 모두 올바른 괄호 수열을 만들었다는 것을 알았지만, 자신의 수열이 올바른지는 알지 못했다.

디마는 과제 설명에서 "올바른"이라는 단어를 놓쳤다고 생각해서, 수열을 조금 고쳐 상황을 바로잡으려 한다. 그는 재배열 연산을 임의의 횟수만큼 (0번도 가능) 수행할 수 있다. 재배열 연산은 수열의 임의의 부분 구간을 골라 그 안의 문자를 임의의 순서로 다시 배열하는 것이다. 이 연산은 $l$ 나노초가 걸리며, 여기서 $l$은 재배열한 부분 구간의 길이이다. 재배열은 여는 괄호와 닫는 괄호의 개수를 바꾸지 않는다.

디마는 곧 답해야 하므로 수열을 가능한 한 빨리 올바르게 만들고자 한다. 그를 도와 올바른 수열을 만들거나, 그것이 불가능하다는 것을 밝혀라.

첫 줄에 정수 $n$ ($1 \le n \le 10^6$)이 주어진다. 디마 수열의 길이이다. 둘째 줄에는 길이가 $n$인 문자열이 주어지며, 이 문자열은 (와 )로만 이루어져 있다.

수열을 올바르게 만드는 데 필요한 최소 나노초 수를 출력한다. 불가능하면 -1을 출력한다.

괄호 수열에 "+"와 "1"을 넣어 잘 구성된 수학 식을 만들 수 있으면 그 수열을 올바르다고 한다. 예를 들어 (())(), (), (()(()))는 올바르고, )(, ((), (()))(는 올바르지 않다.