G - Generando cadena homogénea

Time limit: 2 s
Memory limit: 256 MiB
Languages: C, C++, Java, Haskell, ... (details)

Se tiene una cadena $S$ $(1 \leq |S| \leq 10^5)$ conteniendo solamente las letras a y b . La cadena $S$ puede ser transformada escogiendo un intervalo y cambiando las letras (donde hay una a se pone una b y donde hay una b se pone una a ). Se quiere determinar la menor cantidad de transformaciones que luego de aplicadas a $S$ resultan en una cadena que contiene todas las letras iguales.

Input

Línea 1 : Una cadena $S$ formada con letras a y b $(1 \leq |S| \leq 10^5)$.

Output

Línea 1 : Un entero no negativo, la menor cantidad de transformaciones que hay que aplicar a $S$, de forma tal que la cadena resultante tenga todas las letras iguales.

Sample test(s)

Input
abba
Output
1
Input
aaaaa
Output
0