Вам дана бинарная строка \(S\) длины \(n\), индексированная от \(1\) до \(n\). Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):
Выберите два целых числа \(l\) и \(r\) (\(1 \le l \le r \le n\)). Пусть \(cnt_0\) это количество вхождений 0 в \(S[l \ldots r]\), а \(cnt_1\) это количество вхождений 1 в \(S[l \ldots r]\). Вы можете заплатить \(|cnt_0 - cnt_1| + 1\) монет и отсортировать \(S[l \ldots r]\). (Как \(S[l \ldots r]\) мы обозначаем подстроку \(S\), начинающуюся в позиции \(l\) и заканчивающуюся в позиции \(r\)).
Например, если \(S = \) 11001, мы можем выполнить операцию над \(S[2 \ldots 4]\) за \(|2 - 1| + 1 = 2\) монеты и получить \(S = \) 10011 в качестве новой строки.
Найдите минимальное общее количество монет, необходимое для сортировки \(S\) в возрастающем порядке.
Выходные данные
Для каждого набора входных данных выведите минимальное общее количество монет, необходимое для сортировки \(S\) в возрастающем порядке.
Примечание
В первом наборе входных данных \(S\) уже отсортирована.
Во втором наборе входных данных достаточно применить операцию с \(l = 1, r = 2\).
В третьем наборе входных данных достаточно применить операцию с \(l = 1, r = 2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1
1
2
10
3
101
4
1000
5
11010
6
110000
20
01000010001010011000
|
0
1
1
3
2
2
5
|