CF1746B.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 \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?

你有一个长度为 $n$ 的数组 $a$，其中仅包含 $0$ 和 $1$。你可以执行以下操作：

• 选择两个下标 $1 \le i , j \le n$，且 $i \ne j$，
• 将 $a_{i}$ 加到 $a_{j}$ 上，
• 从 $a$ 中删除 $a_{i}$。

注意：执行若干次操作后，$a$ 中的元素可能大于 $1$。此外，每次操作后 $n$ 减少 $1$。

要使 $a$ 变为非递减（即每个元素都不小于前一个元素），所需的最少操作次数是多少？

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组 $a$ 的大小。

下一行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$（每个 $a_i$ 为 $0$ 或 $1$），即数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

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

对于每个测试用例，输出一个整数，表示使 $a$ 非递减所需的最少操作次数。

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.

在第一个测试用例中，$a$ 已经是非递减的，因此无需执行任何操作，答案为 $0$。

在第二个测试用例中，你可以对 $i = 1$ 和 $j = 5$ 执行一次操作，使得 $a$ 变为 $[0, 0, 1, 2]$，此时它成为非递减序列。

在第三个测试用例中，你可以对 $i = 2$ 和 $j = 1$ 执行一次操作，使得 $a$ 变为 $[1]$，此时它成为非递减序列。