괄호 부분 문자열

괄호 문자열은 다음과 같이 정의한다.

1. 빈 문자열은 괄호 문자열이다.
2. $S$가 괄호 문자열이면 $(S)$도 괄호 문자열이다.
3. $S$와 $T$가 괄호 문자열이면 $ST$도 괄호 문자열이다.
4. 괄호 문자열은 위 세 규칙으로만 만들어진다.

예를 들어 ()()와 ((()))(())는 괄호 문자열이고, )((), (((((, ())는 괄호 문자열이 아니다.

문자열 $S$가 주어지면 $S$의 부분 문자열 중 괄호 문자열인 것이 몇 종류인지 세는 프로그램을 작성하시오. 부분 문자열은 $S$에서 연속한 구간을 잘라낸 문자열이고, 빈 문자열은 세지 않는다. 같은 문자열이 여러 위치에 나타나도 한 번만 센다.

첫째 줄에 문자열의 길이 $N$ ($1 \le N \le 500{,}000$)이 주어진다.

둘째 줄에 문자열 $S$가 주어진다. $S$의 길이는 $N$이고, 여는 괄호 (와 닫는 괄호 )로만 이루어져 있다.

첫째 줄에 $S$의 부분 문자열 중 서로 다른 괄호 문자열의 개수를 출력한다.