Typo

Kipa loves valid bracket strings and recently bought a laptop. Because the keyboard was so small, Kipa worries that an opening bracket ( and a closing bracket ) might have been typed the wrong way around. Kipa typed very carefully, so there was at most one typo.

Given the bracket string Kipa typed, help Kipa by counting how many different positions there are at which changing a single character — turning an opening bracket into a closing bracket, or a closing bracket into an opening bracket — makes the whole string a valid bracket string.

A valid bracket string is defined as follows.

• () is a valid bracket string.
• If a string A is a valid bracket string, then (A) is also a valid bracket string.
• If strings A and B are both valid bracket strings, then their concatenation AB is also a valid bracket string.

The first line contains the bracket string Kipa typed. It consists only of ( and ), and its length $n$ satisfies $1 \le n \le 100000$.

Print, on the first line, the number of positions at which changing exactly one character makes the string a valid bracket string. If there is no such position, print 0.

Consider the string ()(()))) that Kipa typed. The position of each character is shown below.

pos:  1 2 3 4 5 6 7 8
char: ( ) ( ( ) ) ) )

Changing the $2$nd character ) to ( gives the valid bracket string (((()))). In the same way, changing the $5$th, $6$th, or $7$th character also produces a valid bracket string, so the answer is $4$.