북극곰은 괄호를 찢어

시간 제한1초메모리 제한1024 MB

요약

밤마다 괄호 사이에 O와 X를 놓으면 북극곰이 O를 ()로, X를 )(로 바꾼다. 원하는 문자열 S를 최소 며칠 만에 얻거나 불가능하면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: 스택, 그리디
정답자: 아직 제출이 없습니다

문제

극지 연구소에서 연구 중인 협이는 새로운 북극곰의 특성을 발견했다. 그것은 바로 북극곰이 $O$ 와 $X$ 를 보면 $()$ 와 $)($ 로 찢어버린다는 것이다.

협이는 이러한 북극곰의 특성을 이용하여 길이 $N$ 의 괄호 문자열 $S$ 를 만들고자 한다. 북극곰은 낮에 활동을 하기 때문에 낮에 돌아다니는 것은 위험하다. 때문에 협이는 매일 밤마다 활동할 수 있다. 밤에 협이는 문자열이 있으면 그 위에 $O$ 또는 $X$ 를 원하는 만큼 놓을 수 있다. 그러면 낮에 북극곰이 와서 문자들을 모두 찢어 놓는다.

예를 들어 이미 문자열 $()()$ 가 있다고 생각해보자. 밤에 문자를 $(O)X(O)$ 다음과 같이 놓아둔다면 하루가 지나 $(()))((())$ 와 같은 문자열이 된다.

이때 원하는 문자열을 만들려면 최소 며칠이 걸리는지 계산해보자.

입력

입력은 아래와 같이 주어진다.

$N$

$S$

출력

원하는 문자열을 만들기 위해 걸리는 최소 일수를 구하라.

원하는 문자열을 만들 수 없다면 -1을 출력한다.

제한

$1\leq N\leq 200\\,000$
$S$ 는 '(' 또는 ')'로 이루어져 있다.

예제3

예제 1
입력
```
6
()()()
```
예상 출력
```
1
```
예제 2
입력
```
10
(()))((())
```
예상 출력
```
2
```
예제 3
입력
```
3
(()
```
예상 출력
```
-1
```