덜렁대는 소들

소 Bessie는 새 노트북에 균형 잡힌 괄호 문자열을 입력하려고 하지만, 발굽이 커서 서툰 탓에 문자를 자꾸 잘못 입력합니다. 문자열이 균형을 이루도록 하려면 최소 몇 개의 문자를 뒤집어야(예: 여는 괄호를 닫는 괄호로, 또는 그 반대로 바꾸는 것) 하는지 구해 그녀를 도와주세요.

괄호 문자열이 "균형 잡혔다(balanced)"라는 것을 정의하는 방법은 여러 가지가 있습니다. 가장 간단한 정의는 다음과 같습니다. ( 와 ) 의 총 개수가 서로 같아야 하고, 문자열의 모든 접두사(prefix)에서 ( 의 개수가 ) 의 개수 이상이어야 합니다. 예를 들어 다음 문자열들은 모두 균형 잡혀 있습니다.

• ()
• (())
• ()(()())

반면 다음 문자열들은 균형 잡혀 있지 않습니다.

• )(
• ())(
• ((())))

• 첫째 줄: 길이가 짝수이고 최대 100,000자인 괄호 문자열.

• 첫째 줄: 문자열을 균형 잡힌 문자열로 바꾸기 위해 뒤집어야 하는 괄호의 최소 개수를 나타내는 정수 하나.

출력 설명

마지막 괄호를 반드시 뒤집어야 하고, 가운데에 있는 두 개의 닫는 괄호 중 하나도 뒤집어야 합니다.