Задана двоичная строка $$$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$$$.
