괄호 표현식

괄호 표현식은 여는 괄호 (와 닫는 괄호 )로만 이루어진, 비어 있지 않은 문자열입니다. 어떤 괄호 표현식에서 모든 여는 괄호를 자기보다 뒤에 있는 어떤 닫는 괄호와 짝지을 수 있고, 각 짝 사이에 놓인 괄호들도 다시 올바른 괄호 표현식을 이룬다면, 그 표현식을 올바른 괄호 표현식이라고 부릅니다.

예를 들어 (()())()는 올바른 괄호 표현식이지만, )(와 ()(는 올바르지 않습니다.

Bajtazar는 연구를 위해 어떤 프로그램을 실행했고, 그 프로그램은 연구에 꼭 필요한 하나의 올바른 괄호 표현식 $S$를 출력했습니다. 그런데 이 문자열이, 우연히 그 앞뒤로 함께 출력된 수많은 다른 괄호들 사이에 묻혀 사라져 버렸습니다. 결국 Bajtazar에게는 찾고 있는 $S$를 연속된 부분 문자열로 포함하는 하나의 긴 괄호 문자열만 남았지만, $S$가 어디에서 시작하고 어디에서 끝나는지는 알 수 없게 되었습니다.

절망에 빠진 그는 주어진 문자열 안에서 올바른 괄호 표현식이 될 수 있는 모든 위치를 찾아 달라고 부탁했습니다. 그런 위치가 많지 않기를 바라면서 말이죠.

주어진 문자열의 연속된 부분 문자열 중에서 올바른 괄호 표현식인 것이 몇 개인지 세어 주세요.

첫째 줄에 Bajtazar가 읽은 문자열의 길이를 나타내는 정수 $n$ ($1 \le n \le 2\,000\,000$)이 주어집니다. 둘째 줄에는 공백 없이 $n$개의 괄호로 이루어진 괄호 문자열이 주어집니다.

주어진 문자열의 연속된 부분 문자열 중에서 올바른 괄호 표현식인 것의 개수를 정수 하나로 출력합니다.