Moving Chips
Contest: Educational Codeforces Round 162 (Rated for Div. 2)
Difficulty rating: 800
Tags: greedy, implementation

There is a ribbon divided into $$$n$$$ cells, numbered from $$$1$$$ to $$$n$$$ from left to right. Each cell either contains a chip or is free.

You can perform the following operation any number of times (possibly zero): choose a chip and move it to the closest free cell to the left. You can choose any chip that you want, provided that there is at least one free cell to the left of it. When you move the chip, the cell where it was before the operation becomes free.

Your goal is to move the chips in such a way that they form a single block, without any free cells between them. What is the minimum number of operations you have to perform?

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case consists of two lines:

- the first line contains one integer $$$n$$$ ($$$2 \le n \le 50$$$) — the number of cells;
- the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$); $$$a_i = 0$$$ means that the $$$i$$$-th cell is free; $$$a_i = 1$$$ means that the $$$i$$$-th cell contains a chip.

Additional constraint on the input: in each test case, at least one cell contains a chip.

Output format:
For each test case, print one integer — the minimum number of operations you have to perform so that all chips form a single block without any free cells between them.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example, you can perform the operation on the chip in the $$$7$$$-th cell. The closest free cell to the left is the $$$5$$$-th cell, so it moves there. After that, all chips form a single block.

In the second example, all chips are already in a single block. Same for the third example.

Example input:
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

Example output:
1
0
0
2
3

Editorial:
Denote the position of the leftmost chip as $$$l$$$, the position of the rightmost chip as $$$r$$$, and the number of chips as $$$c$$$.
Having all chips in one block without free spaces means that we need to reach the situation when $$$r - l = c - 1$$$. Since $$$r - l \ge c - 1$$$ is always met (the situation when $$$r-l = c-1$$$ is when the chips are packed as close as possible), we need to decrease the value of $$$r-l$$$ as fast as possible.
There are two approaches to do it. One is to try decreasing $$$r$$$ every time; i. e. let's code a greedy solution that always applies an operation to the current rightmost chip. This is actually one of the correct solutions to the problem.
But if we prove it, we can design an easier solution. Whenever we apply an operation on any chip other than the rightmost chip, the value of $$$r-l$$$ does not decrease (we either don't change $$$l$$$ and $$$r$$$ at all, or decrease $$$l$$$). But whenever we apply an operation on the rightmost chip, $$$r$$$ decreases by exactly $$$1$$$ (the new rightmost chip will be in position $$$r-1$$$ — either it is present there before the operation, or it will be moved there from $$$r$$$). So, only applying the operations to the rightmost chip decreases $$$r-l$$$, and it always decreases $$$r-l$$$ by exactly $$$1$$$ no matter what. So, the answer to the problem is actually $$$(r-l) - (c-1)$$$.