D. Сбалансированная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана двоичная строка $$$s$$$ (двоичная строка — это строка, состоящая из символов 0 и/или 1).

Давайте назовем двоичную строку сбалансированной, если число подпоследовательностей 01 (число таких пар индексов $$$i$$$ и $$$j$$$, что $$$1 \le i < j \le n$$$, $$$s_i=0$$$ и $$$s_j=1$$$) равно числу подпоследовательностей 10 (число таких пар индексов $$$k$$$ и $$$l$$$, что $$$1 \le k < l \le n$$$, $$$s_k=1$$$ и $$$s_l=0$$$) в строке.

Например, строка 1000110 является сбалансированной, поскольку и количество подпоследовательностей 01, и количество подпоследовательностей 10 равно $$$6$$$. С другой стороны, 11010 не сбалансирована, потому что количество подпоследовательностей 01 равно $$$1$$$, а количество подпоследовательностей 10 равно $$$5$$$.

Вы можете выполнить следующую операцию любое количество раз (возможно, ноль): выбрать два символа в строке $$$s$$$ и поменять их местами. Ваша задача — посчитайте минимальное количество вышеописанных операций, чтобы строка $$$s$$$ стала сбалансированной.

Входные данные

Единственная строка входных данных содержит $$$s$$$ ($$$3 \le |s| \le 100$$$) — последовательность из символов 0 и/или 1.

Дополнительное ограничение на входные данные: $$$s$$$ можно сделать сбалансированной.

Выходные данные

Выведите одно целое число — минимальное количество операций, чтобы строка $$$s$$$ стала сбалансированной.

Примеры
Входные данные
101
Выходные данные
0
Входные данные
1000110
Выходные данные
0
Входные данные
11010
Выходные данные
1
Входные данные
11001100
Выходные данные
2
Примечание

В первом примере строка уже сбалансированная: и количество 01, и количество 10 равно $$$1$$$.

Во втором примере строка уже сбалансированная: и количество 01, и количество 10 равно $$$6$$$.

В третьем примере один из возможных ответов — следующий: 11010 $$$\rightarrow$$$ 01110. После этого и количество 01, и количество 10 равно $$$3$$$.

В четвертом примере один из возможных ответов — следующий: 11001100 $$$\rightarrow$$$ 11001010 $$$\rightarrow$$$ 11000011. После этого и количество 01, и количество 10 равно $$$8$$$.