괄호

$N$ 개의 여는 괄호와 $N$ 개의 닫는 괄호로 구성된 문자열이 주어진다. 문자열에 할 수 있는 작업은 아래 두 가지이다.

• 인접한 두 괄호를 교환한다. 여는 괄호든 닫는 괄호든 상관 없이 교환이 가능하다.
• 인접하고 짝이 맞는 괄호 한 쌍을 제거한다. 즉, 여는 괄호, 닫는 괄호 순서로 인접한 괄호쌍을 제거한다. 제거되고 나면 문자열은 압축된다. 즉 빈 자리는 없다.

두 작업은 원하는 순서로 임의로 진행할 수 있다. 모든 문자를 제거하는 최소 작업 횟수를 구하라.

입력 형식

첫 줄에 괄호의 수를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 500\,000$)

그다음 줄에 $N$ 개의 여는 괄호와 $N$ 개의 닫는 괄호로 이루어진 길이 $2N$의 문자열이 주어진다. 주어지는 괄호 문자는 () 중 하나다.

출력 형식

첫 줄에 두 작업을 원하는 순서로 자유롭게 진행하여 모든 문자를 제거하는 최소 작업 횟수를 출력한다.

예제 1

3
())()(

4

예제 2

5
()(())(())

5

예제 3

5
)()(()))((

7

예제 설명

예제 1에서, 네 번째와 다섯 번째의 짝이 맞는 쌍을 제거하고 나면 문자열은 ())(이 된다. 문자열에서 세 번째와 네 번째 글자를 교환하면 문자열은 ()()이 된다. 이제 짝이 맞는 쌍을 두 번 제거하면 모든 문자를 제거한 것이다. 따라서, 이 경우의 답은 $4$가 된다.

예제 2에서, 짝이 맞는 쌍을 계속 제거하면 다섯 번의 작업으로 모든 문자를 제거할 수 있음을 알 수 있다.

예제 3에서, 마지막에서 두 번째와 세 번째 글자를 교환하면 문자열은 )()(())()(이 된다. 짝이 맞는 쌍을 제거하는 것을 네 번 반복하면 문자열은 )(이 된다. 여기서 두 문자를 교환하고 짝이 맞는 쌍을 제거할 수 있다. 작업의 횟수는 $7$ 번이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설