Есть книжная полка, на которой может уместиться \(n\) книг. \(i\)-я позиция на книжной полке \(a_i = 1\), если на этой позиции находится книга, и \(a_i = 0\) иначе. Гарантируется, что есть как минимум одна книга на книжной полке.
За один ход вы можете выбрать какой-то непрерывный отрезок \([l; r]\), состоящий из книг (то есть для каждого \(i\) от \(l\) до \(r\) должно выполняться условие \(a_i = 1\)), и:
- Сдвинуть его вправо на \(1\): переместить книгу с индекса \(i\) в \(i + 1\) для всех \(l \le i \le r\). Этот ход можно свершить только тогда, когда \(r+1 \le n\) и на позиции \(r+1\) нет книги.
- Сдвинуть его влево на \(1\): переместить книгу с индекса \(i\) в \(i-1\) для всех \(l \le i \le r\). Этот ход можно свершить только тогда, когда \(l-1 \ge 1\) и на позиции \(l-1\) нет книги.
Ваша задача — найти минимальное количество ходов, необходимое, чтобы собрать все книги на полке в непрерывный (последовательный) отрезок (т.е. отрезок без промежутков).
Например, в \(a = [0, 0, 1, 0, 1]\) есть промежуток между книгами (\(a_4 = 0\) при \(a_3 = 1\) и \(a_5 = 1\)), в \(a = [1, 1, 0]\) нет промежутков между книгами и в \(a = [0, 0,0]\) тоже нет промежутков между книгами.
Вам нужно ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите одно целое число: минимальное количество ходов, необходимое, чтобы собрать все книги на полке в непрерывный (последовательный) отрезок (т.е. отрезок без промежутков).
Примечание
В первом наборе тестовых данных примера вы можете сдвинуть отрезок \([3; 3]\) вправо, а затем отрезок \([4; 5]\) вправо. После всех ходов книги будут образовывать непрерывный отрезок \([5; 7]\). Таким образом, ответ равен \(2\).
Во втором наборе тестовых данных примера вам ничего не нужно делать, так как все книги на книжной полке уже образуют непрерывный отрезок.
В третьем наборе тестовых данных примера вы можете сдвинуть отрезок \([5; 5]\) влево, затем отрезок \([4; 4]\) опять влево. После всех ходов книги будут образовывать непрерывный отрезок \([1; 3]\). Таким образом, ответ равен \(2\).
В четвертом наборе тестовых данных примера вы можете сдвинуть отрезок \([1; 1]\) вправо, отрезок \([2; 2]\) вправо, отрезок \([6; 6]\) влево и, наконец, отрезок \([5; 5]\) влево. После всех ходов книги будут образовывать непрерывный отрезок \([3; 4]\). Таким образом, ответ равен \(4\).
В пятом наборе тестовых данных примера вы можете сдвинуть отрезок \([1; 2]\) вправо. После всех ходов книги будут образовывать непрерывный отрезок \([2; 5]\). Таким образом, ответ равен \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
7
0 0 1 0 1 0 1
3
1 0 0
5
1 1 0 0 1
6
1 0 0 0 0 1
5
1 1 0 1 1
|
2
0
2
4
1
|