소를 찾아라

천방지축 베시(소, 1세)가 외양간을 탈출해 풀로 뒤덮인 산등성이에 숨었다. 농부 존은 온 풀숲을 샅샅이 뒤졌지만 베시를 찾지 못했다. 존의 눈에는 그 풀밭이 $N$개의 소괄호로 이루어진 문자열처럼 보였기 때문이다. 예를 들면 다음과 같다.

)((()())())

존은 베시의 두 뒷다리가 서로 붙어 있는 왼쪽 소괄호 두 개 (( 와 똑같이 생겼고, 두 앞다리가 서로 붙어 있는 오른쪽 소괄호 두 개 )) 와 똑같이 생겼다는 것을 안다. 문자열에서 (( 가 시작하는 위치(인덱스)를 $x$, )) 가 시작하는 위치(인덱스)를 $y$라 할 때, 베시가 서 있는 자리는 $x < y$인 순서쌍 $(x, y)$로 나타낼 수 있다.

베시가 서 있을 수 있는 서로 다른 순서쌍 $(x, y)$의 개수를 구해 존을 도와주자.

첫째 줄에 소괄호로만 이루어진 길이 $N$의 문자열이 주어진다. ($1 \le N \le 50{,}000$)

첫째 줄에 베시가 서 있을 수 있는 자리의 개수를 출력한다. 즉, (( 가 시작하는 인덱스 $x$와 )) 가 시작하는 인덱스 $y$에 대해 $x < y$인 서로 다른 순서쌍 $(x, y)$의 개수를 출력한다.

예를 들어 문자열 )((()())()) 에서 (( 는 인덱스 1과 2에서 시작하고, )) 는 인덱스 6과 9에서 시작한다(0부터 셈). 모든 (( 가 모든 )) 보다 앞에 있으므로 만들 수 있는 순서쌍은 $2 \times 2 = 4$개다.