CF 1746B - Rebellion

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, i≠j,add ai to aj,remove ai 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

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.

The first line of each test case contains an integer n (1≤n≤105), the size of array a.

Next line contains n integers a1,a2,…an (ai is 0 or 1), elements of array a.

It's guaranteed that sum of n over all test cases doesn't exceed 2⋅105.

Output

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

----------------------------------------

您有一个大小为 n 的数组 a，仅由 0 和 1 组成。 您可以进行以下操作：

选择两个索引1≤i，j≤n，i≠j，将ai添加到aj，从a中删除ai。

请注意，执行某些操作后，a 的元素可能会变得大于 1。 另请注意，运算后 n 会减 1。

进行非递减运算所需的最少操作次数是多少，即？ e. 每个元素不小于前一个元素？

输入

每个测试包含多个测试用例。 第一行包含测试用例的数量 t (1≤t≤104)。 测试用例的描述如下。

每个测试用例的第一行包含一个整数n（1≤n≤105），即数组a的大小。

下一行包含 n 个整数 a1,a2,…an（ai 为 0 或 1），数组 a 的元素。

保证所有测试用例的 n 之和不超过 2⋅105。

输出

对于每个测试用例打印一个整数，实现非递减所需的最小操作数。

-----------------------双指针处理；

下面是代码：