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. ()(( β†’ ()() β‡’ 1 modification
  1. )( β†’ () β‡’ 2 modifications
  1. ()() β‡’ no modifications needed
  1. ((() β†’ ()() β‡’ 2 modifications
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue