← Home
write a go solution for Description:
You have an array a of size n consisting only of zeroes and ones. You can do the following operation:

- choose two indices 1<=i,j<=n, inej,
- 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<=t<=10^4). The description of the test cases follows.

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

Next line contains n integers a_1,a_2,ldotsa_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*10^5.

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

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.. Output only the code with no comments, explanation, or additional text.