Bracket Sequence Correction

Problem Description:

Little A accidentally inserted an extra bracket into his valid bracket sequence, and now the sequence may no longer be valid. Given a string s consisting only of characters ( and ), it is guaranteed that s was obtained from a valid parentheses sequence by inserting exactly one extra bracket.

Your task is to determine the number of ways to remove exactly one bracket (i.e. remove one character from the string) so that the resulting sequence becomes a valid bracket sequence.

A valid bracket sequence is defined as follows:

1. The empty string is valid.
2. If A is valid, then (A) is also valid.
3. If A and B are valid, then the concatenation AB is also valid.

You need to count the number of indices i (1-indexed for explanation) such that if you remove the character at position i from s, the resulting string is a valid bracket sequence.

Note: It is guaranteed that s is formed by inserting exactly one extra bracket into a valid sequence, so the overall imbalance of the brackets is either +1 (one extra '(') or -1 (one extra ')').

inputFormat

Input Format:

A single line containing the non-empty string s (with 1 ≤ |s| ≤ 10⁵), consisting only of the characters ( and ).

outputFormat

Output Format:

Output a single integer representing the number of ways to remove exactly one bracket so that the remaining sequence is a valid bracket sequence.

sample

(()))

2