Задана двоичная строка \(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\) стала сбалансированной.
Примечание
В первом примере строка уже сбалансированная: и количество 01, и количество 10 равно \(1\).
Во втором примере строка уже сбалансированная: и количество 01, и количество 10 равно \(6\).
В третьем примере один из возможных ответов — следующий: 11010 \(\rightarrow\) 01110. После этого и количество 01, и количество 10 равно \(3\).
В четвертом примере один из возможных ответов — следующий: 11001100 \(\rightarrow\) 11001010 \(\rightarrow\) 11000011. После этого и количество 01, и количество 10 равно \(8\).