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

  2. )( → () ⇒ 2 modifications

  3. ()() ⇒ no modifications needed

  4. ((() → ()() ⇒ 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