#89Medium
Bracket balance
Time: 1 s · Memory: 256 MB
- Strings
Statement
You are given a string of Latin letters and brackets (, ). Are the brackets placed correctly? Every ) closes the nearest unmatched ( before it.
- If everything is correct —
0. - If some
)has no pair — the position of the first such)(counting from ). - If every
)has a pair but some(stay unclosed —-1.
Input format
A single line — a string of to characters: lowercase Latin letters, ( and ).
Output format
A single integer.
Examples
Input
(((yfgfs))p)
Output
0
Input
((())))(
Output
7
Note
Keep a counter of open brackets: ( adds , ) subtracts . The place where the counter becomes negative is an unmatched ). If the counter is above at the end, some ( are unclosed. In the second example the extra ) is character 7: the answer is .
