Rebellion
Contest: Codeforces Global Round 23
Difficulty rating: 800
Tags: constructive algorithms, greedy, two pointers

You have an array $$$a$$$ of size $$$n$$$ consisting only of zeroes and ones. You can do the following operation:

- choose two indices $$$1 \le i , j \le n$$$, $$$i \ne j$$$,
- add $$$a_{i}$$$ to $$$a_{j}$$$,
- remove $$$a_{i}$$$ from $$$a$$$.

Note that elements of $$$a$$$ can become bigger than $$$1$$$ after performing some operations. Also note that $$$n$$$ becomes $$$1$$$ less after the operation.

What is the minimum number of operations needed to make $$$a$$$ non-decreasing, i. e. that each element is not less than the previous element?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the size of array $$$a$$$.

Next line contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots a_{n}$$$ ($$$a_i$$$ is $$$0$$$ or $$$1$$$), elements of array $$$a$$$.

It's guaranteed that sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case print a single integer, minimum number of operations needed to make $$$a$$$ non-decreasing.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$a$$$ is already non-decreasing, so you don't need to do any operations and the answer is $$$0$$$.

In the second test case, you can perform an operation for $$$i = 1$$$ and $$$j = 5$$$, so $$$a$$$ will be equal to $$$[0, 0, 1, 2]$$$ and it becomes non-decreasing.

In the third test case, you can perform an operation for $$$i = 2$$$ and $$$j = 1$$$, so $$$a$$$ will be equal to $$$[1]$$$ and it becomes non-decreasing.

Example input:
4
8
0 0 1 1 1 1 1 1
5
1 0 0 1 1
2
1 0
11
1 1 0 0 1 0 0 1 1 1 0

Example output:
0
1
1
3

Editorial:
Step 1:
problem/hint:
Assume that $$$a_{i} = 0$$$ for each $$$1 \le i \le n$$$, what should we do?
solution:
Nothing! The array is already sorted and the answer is $$$0$$$.
Step 2:
problem/hint:
After sorting the array, consider the first non-zero element of $$$a$$$, how many elements after that are equal to zero? In other words, consider smallest $$$i$$$ such that $$$a_{i} > 0$$$, how many indices $$$k$$$ exist such that $$$i < k$$$ and $$$a_{k} = 0$$$?
solution:
0, because we call an array $$$a$$$ sorted (in non-decreasing order), if for all $$$1 \le i < j \le n$$$, $$$a_{i} \le a_{j}$$$ holds. So all numbers after leftmost non-zero element must be non-zero too.
Step 3:
problem/hint:
assume that after sorting $$$a$$$, $$$a_{i}$$$ ($$$1 \le i \le n$$$) is the leftmost non-zero element. Define $$$G_{1}$$$ as the set of indices $$$j$$$ such that $$$1 \le j < i$$$ and $$$a_{j} > 0$$$ at the beginning, also define $$$G_{2}$$$ as the set of indices $$$j$$$ such that $$$i < j \le n$$$ and $$$a_{j} = 0$$$ at the beginning. What is the answer?
solution:
$$$max(|G_{1}|, |G_{2}|)$$$. It's obvious that in one operation at most one element will be deleted from each group. So we must perform at least $$$max(|G_{1}|, |G_{2}|)$$$ operations. Now we want to show that it's sufficient too. There are three cases:
1. $$$min(|G_{1}|, |G_{2}|) > 1$$$, at this point, we know that all elements of $$$a$$$ are $$$0$$$ or $$$1$$$. So we can pick one element from $$$G_{1}$$$ and add it to an element from $$$G_{2}$$$, so the size of both groups will decrease by $$$1$$$. It's obvious that all elements of $$$a$$$ will remain less than or equal to $$$1$$$ after this operation.
2. $$$|G_{1}| = 0$$$, it's easy to see that we can add $$$a[k]$$$ ($$$k \in G_{2}$$$) to a random element. So $$$|G_{2}|$$$ will decrease by $$$1$$$.
3. $$$|G_{2}| = 0$$$, it's easy to see that we can add $$$a[k]$$$ ($$$k \in G_{1}$$$) to the last element of $$$a$$$. So $$$|G_{1}|$$$ will decrease by $$$1$$$.
Step 4:
problem/hint:
Now how can we solve the problem using previous steps?
solution:
If all elements are equal to $$$0$$$, the answer is obviously zero. Otherwise we will calculate two arrays, number of ones in each prefix and number of zeros in each suffix. We will also fix the leftmost non-zero element and calculate the answer for it easily by using Step 3 algorithm in O(n).