소를 찾아라

천방지축 베시(소, 1세)는 외양간을 탈출해서 풀로 뒤덮인 산등성이에 숨었다. 농부인 존씨는 베시를 다시 잡기위해 온 풀숲을 샅샅히 뒤졌지만 찾지 못하였다. 안타깝게도 그는 베시를 찾는데 어려워하고 있다. 존에게 그 풀밭은 N개의 소괄호로 이루어진 문자열처럼 보였기 때문이다. 예를 들면, 아래와 같다.

)((()())())

존은 베시의 뒷다리가 왼쪽 소괄호 두 개가 붙어있는 것 (( 과 똑같이 생긴 것을 알고있다. 또한 베시의 앞다리는 오른쪽 소괄호 두 개가 붙어있는 것 )) 과 똑같이 생겼다. 베시의 위치는 뒷다리의 위치가 x이고 앞다리의 위치가 y라고 할때 x < y가 되는 쌍으로 표현될 수 있다.

이때, 베시가 서있는 위치가 될 수 있는 서로 다른 순서쌍들의 개수를 구하여 존을 도와보자.

첫 째줄에 N개의 소괄호로 이루어진 문자열이 주어진다. (1 ≤ N ≤ 50,000)

첫 째줄에 베시가 서있을 수 있는 위치의 개수를 출력한다. (즉,  가 나타나는 곳의 인덱스 x와 가 나타나는 곳의 인덱스 y에서 x<y가 되는 서로 다른 순서쌍들의 개수를 출력한다.)

예제에서 베시가 있을 수 있는 곳은 아래의 네가지이다.

1. )()(())
2. )()(())
3. )()())(
4. )()())(