Given a word made up of only opening and closing parentheses, we must make it a correct parenthesization. The only allowed operation is turning each parenthesis, that is, changing its orientation. What is the minimum number of turns needed?

For example, if the word is “`)(()((()`”,
then we can achieve the correct parenthesization “`((())())`”
just turning three parentheses,
and we cannot do better.

**Input**

Input consists of several cases,
each with a word with *n* opening or closing parentheses.
You can assume that *n* is even and between 2 and 100.

**Output**

For every case, print the minimum cost of a correct parenthesization.

**Hint**

Although there are more efficient solutions,
a dynamic programming with time cost Θ(*n*^{3} )
and space cost Θ(*n*^{2} )
should be enough.

Public test cases

**Input**

() ()() (()( )))) ))(( )( )(()((()

**Output**

0 0 1 2 2 2 3

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++