Fix the bracket sequence
Given a string
s of opening and closing brackets, you are allowed to change some opening brackets to closing ones and some closing to opening ones. At least how many operations are necessary to obtain a valid sequence of brackets?Input
The only line of the input contains the string
s (1 ≤ |s| ≤ ). It’s guaranteed that the length of s is even.Output
The program should print the least amount of modifications needed to make the sequence valid.
Examples
Input | Output |
()(( | 1 |
)( | 2 |
()() | 0 |
((() | 1 |
Explanation
- ()(( → ()() ⇒ 1 modification
- )( → () ⇒ 2 modifications
- ()() ⇒ no modifications needed
- ((() → ()() ⇒ 2 modifications
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB