Сегодня Марин пришла на фестиваль косплея и готовится к групповому фотоснимку!
Для группового снимка косплееры выстраиваются в горизонтальный ряд. Групповой снимок считается красивым, если на каждом непрерывном отрезке, включающем хотя бы \(2\) косплееров, количество мужчин не превышает количества женщин (очевидно).
Сейчас ряд состоит из \(n\) косплееров и может быть описан бинарной строкой \(s\). \(i\)-й косплеер — мужчина, если \(s_i = 0\), а женщина, если \(s_i = 1\). Чтобы сделать ряд красивым, вы можете предложить дополнительным косплеерам (возможно, нулю) встать в любое место в ряду. Вы не можете исключать косплееров из ряда.
Марин хочет узнать минимальное количество дополнительных косплееров, которых нужно пригласить, чтобы групповой снимок получился красивым. Она не может сделать это сама, поэтому просит у вас помощи. Сможете ей помочь?
Выходные данные
Для каждого набора входных данных выведите минимальное количество косплееров, которых нужно добавить в ряд, чтобы фото стало красивым.
Примечание
В первом примере для каждой пары подряд стоящих косплееров вы можете пригласить двух девушек-косплееров для того, чтобы они встали между ними. Тогда \(000 \rightarrow 0110110\).
В третьем наборе вы можете пригласить одну девушку-косплеера, чтобы она встала после второго косплеера. Тогда \(010 \rightarrow 0110\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
3
000
3
001
3
010
3
011
3
100
3
101
3
110
3
111
19
1010110000100000101
|
4
2
1
0
2
0
0
0
17
|