Вам дана строка \(s\) длины \(n\), состоящая из символов \(\mathtt{0}\) и \(\mathtt{1}\). За одну операцию вы можете выбрать непустую подпоследовательность \(t\) из \(s\), такую, что любые два соседних символа \(t\) различны. Затем вы инвертируете каждый символ в \(t\) (\(\mathtt{0}\) становится \(\mathtt{1}\), а \(\mathtt{1}\) становится \(\mathtt{0}\)). Например, если \(s=\mathtt{\underline{0}0\underline{101}}\) и \(t=s_1s_3s_4s_5=\mathtt{0101}\), то после операции \(s\) станет \(\mathtt{\underline{1}0\underline{010}}\).
Вычислите минимальное количество операций, необходимых для того, чтобы сделать все символы \(s\) равными \(\mathtt{0}\).
Напомним, что для строки \(s = s_1s_2\ldots s_n\), любая строка \(t=s_{i_1}s_{i_2}\ldots s_{i_k}\) (\(k\ge 1\)), где \(1\leq i_1 < i_2 < \ldots <i_k\leq n\), является подпоследовательностью \(s\).
Выходные данные
Для каждого набора входных данных выведите минимальное количество операций, необходимых для изменения всех символов в \(s\) на \(\mathtt{0}\).
Примечание
В первом наборе входных данных вы можете инвертировать \(s_1\). Строка \(s\) станет \(\mathtt{0}\), поэтому ответ равен \(1\).
В четвертом наборе входных данных вы можете выполнить следующие три операции по порядку:
- Инвертируйте \(s_1s_2s_3s_4s_5\). Тогда \(s\) станет \(\mathtt{\underline{01010}}\).
- Инвертируйте \(s_2s_3s_4\). Тогда \(s\) станет \(\mathtt{0\underline{010}0}\).
- Инвертируйте \(s_3\). Тогда \(s\) станет \(\mathtt{00\underline{0}00}\).
Можно показать, что вы не можете изменить все символы в \(s\) на \(\mathtt{0}\) менее чем за три операции, поэтому ответ равен \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
000
1001
10101
01100101011101
|
1
0
2
3
8
|