Problem B
If Index

Ekko is working on his time-traveling machine to reunite with Powder in a parallel universe. To achieve this, he must write code in a peculiar programming language called C-IF.

C-IF has an extremely minimalistic syntax: the only keyword is if, and the only allowed characters are {, and }, which must always be properly matched. A C-IF program is considered valid if:

• It consists only of if, {, and }.

• It is balanced, which means there are an equal number of { and } characters, and we can pair up each { with a } such that the { character shows up first.

For example, if{{}} and ifif{if} are valid C-IF programs, while xxx, {if, and }if{ are not.

Ekko measures how annoying a C-IF program is using its if-index, defined as follows:

• For each if, compute its nesting depth, defined as the number of {} layers enclosing it

• Given the array of nesting depths, which has $n$ elements, we define the if-index as the element which occupies position number $\lfloor \frac{n + 1}{2}\rfloor $ after we sort the elements in non-decreasing order (where the first element has index $1$ and the last element has index $n$)

• If there are no if statements in the program, we define the if-index to be $-1$

Help Ekko compute the if-index for a valid C-IF program.

Input

The only line of input is a string $S \ (|S| \le 5000)$, a valid C-IF program.

Output

Output one line containing a single number, the if-index of the program $S$.

if

0

if{{ifif}if{if}}

2