도망간 강아지

지훈이가 키우는 강아지 초코는 잔디 밭으로 도망가버렸습니다. 잔디는 N (1 <= N <= 50,000) 괄호의 문자열처럼 보입니다; 

예를 들어:

)((()())())

지훈이는 초코의 뒷다리가 서로 인접한 왼쪽 괄호 ((와 같이 보이고, 그녀의 앞다리가 정확히 두 개의 인접한 오른쪽 괄호 ))와 같이 보인다는 것을 알고 있습니다. 초코의 위치는 따라서 x < y인 두 쌍의 인덱스로 설명할 수 있는데, ((는 x의 위치에서, ))는 y의 위치에서 발견됩니다. 초코가 서 있을 수 있는 다른 가능한 위치의 수를 계산해 주세요.

• 1번째 줄: N (1 <= N <= 50,000)의 길이를 가진 괄호의 문자열.

• 1번째 줄: 초코가 서 있을 수 있는 다른 가능한 위치의 수