Дана строка \(s\), состоящая из символов 0 и/или 1.
Вы должны удалить несколько (возможно, ноль) символов из начала строки и несколько (возможно, ноль) символов с конца. Получившаяся строка может оказаться пустой. Стоимость удаления — это максимум из двух величин:
- количество символов 0, оставшихся в строке;
- количество символов 1, удаленных из строки.
Чему равна минимальная стоимость удаления, которую можно достигнуть?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальную возможную стоимость удаления.
Примечание
Рассмотрим наборы входных данных из примера:
- в первом наборе можно удалить два символа из начала и один символ с конца. Только один 1 был удален, только один 0 остался, поэтому стоимость равна \(1\);
- во втором наборе можно удалить три символа из начала и шесть символов с конца. Два символа 0 останутся, будут удалены три символа 1, поэтому стоимость равна \(3\);
- в третьем наборе входных данных оптимально удалить четыре символа из начала строки;
- в четвертом наборе входных данных оптимально удалить всю строку;
- в пятом наборе входных данных оптимально не удалять ни один символ.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
101110110
1001001001001
0000111111
00000
1111
|
1
3
0
0
0
|