Minimum Swaps to Balance Braces

You are given a string S consisting solely of the characters '{' and '}'. Your task is to compute the minimum number of swaps required to make the string balanced.

A string is considered balanced if for every opening brace { there is a corresponding closing brace } in the proper order. Formally, a balanced string S of length n satisfies the condition that while scanning from left to right, the number of { seen is always greater than or equal to the number of }, and the total counts of both characters are equal.

The formula for the minimum number of required swaps can be expressed in LaTeX as:

$$\text{swaps} = \frac{U_{open} + U_{close}}{2}$$

where U_open is the count of unmatched opening braces and U_close is the count of unmatched closing braces after a single pass through the string.

inputFormat

The input consists of a single line containing the string S (with 1 \leq |S| \leq 10^5), which contains only the characters '{' and '}'.

Formally, the input is:

S

where each character satisfies \(S_i \in \{\{,\}\}\).

outputFormat

Output a single integer representing the minimum number of swaps needed to balance the string. In other words, if after processing, the value is computed as:

$$\text{swaps} = \frac{U_{open} + U_{close}}{2}$$

print this number.

## sample

{}{}

0