Есть лента, разделенная на \(n\) ячеек, пронумерованных слева направо от \(1\) до \(n\). Каждая ячейка либо содержит фишку, либо свободна.
Вы можете выполнять следующую операцию любое количество раз (возможно, ноль): выбрать фишку и переместить ее в ближайшую свободную ячейку слева. Вы можете выбрать любую фишку, при условии, что слева от нее есть хотя бы одна свободная ячейка. При перемещении фишки ячейка, где она находилась до операции, становится свободной.
Ваша цель — переместить фишки таким образом, чтобы они шли подряд, образовывали единый блок без свободных ячеек между ними. Какое минимальное количество операций вам нужно выполнить?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, которые вам нужно выполнить, чтобы все фишки образовали единый блок без свободных ячеек между ними.
Примечание
В первом примере вы можете выполнить операцию с фишкой в \(7\)-й ячейке. Ближайшая свободная ячейка слева — \(5\)-я ячейка, поэтому фишка перемещается туда. После этого все фишки образуют единый блок.
Во втором примере все фишки уже находятся в одном блоке без свободных ячеек между ними. То же самое касается и третьего примера.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
8
0 1 1 1 0 1 1 0
6
0 1 0 0 0 0
6
1 1 1 1 1 1
5
1 0 1 0 1
9
0 1 1 0 0 0 1 1 0
|
1
0
0
2
3
|