Бинарной строкой называется строка, состоящая только из символов 0 и 1. Вам дана бинарная строка \(s_1 s_2 \ldots s_n\). Нужно сделать эту строку неубывающей за наименьшее количество операций. Иными словами, каждый символ должен быть не меньше предыдущего. За одну операцию вы можете сделать следующее:
- Выбрать произвольный индекс в строке \(1 \leq i \leq n\);
- Для всех \(j \geq i\) поменять значение в \(j\)-й позиции на противоположное, то есть если \(s_j = 1\), то сделать \(s_j = 0\), и наоборот.
За какое минимальное количество операций можно сделать строку неубывающей?
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное количество операций, которое потребуется сделать, чтобы сделать строку неубывающей.
Примечание
В первом наборе входных данных строка уже неубывающая.
Во втором наборе входных данных можно выбрать \(i = 1\), и после этого \(s = \mathtt{01}\).
В третьем наборе входных данных можно выбрать \(i = 1\) и получить \(s = \mathtt{010}\), а после этого выбрать \(i = 2\). В результате получим \(s = \mathtt{001}\), то есть неубывающую строку.
В шестом наборе входных данных можно на первой итерации выбрать \(i = 5\) и получить \(s = \mathtt{100001}\). Затем выбрать \(i = 2\), тогда \(s = \mathtt{111110}\). Дальше выбираем \(i = 1\), и получаем неубывающую строку \(s = \mathtt{000001}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
1
1
2
10
3
101
4
1100
5
11001
6
100010
10
0000110000
7
0101010
|
0
1
2
1
2
3
1
5
|