Find the Cow

The reckless calf Bessie (age 1) has escaped the barn and hidden on a grassy hillside. Farmer John searched every clump of grass but could not find her, because to John the field looks like a string of $N$ parentheses. For example:

)((()())())

John knows that Bessie's two hind legs look exactly like two adjacent opening parentheses ((, and her two front legs look exactly like two adjacent closing parentheses )). If $x$ is the index where an (( begins and $y$ is the index where a )) begins, then a spot where Bessie could be standing is an ordered pair $(x, y)$ with $x < y$.

Help John by counting the number of distinct ordered pairs $(x, y)$ where Bessie could be standing.

The first line contains a string of length $N$ consisting only of parentheses. ($1 \le N \le 50{,}000$)

Print the number of spots where Bessie could stand — that is, the number of distinct ordered pairs $(x, y)$ where $x$ is the starting index of an (( and $y$ is the starting index of a )) with $x < y$.

For the string )((()())()), the (( patterns begin at indices 1 and 2, and the )) patterns begin at indices 6 and 9 (0-indexed). Every (( comes before every )), so the number of valid pairs is $2 \times 2 = 4$.