题目描述

你有一个大小为 $n$ 的数组 $a$，其中只包含 $0$ 和 $1$。你可以进行如下操作：

• 选择两个下标 $1 \le i, j \le n$，且 $i \ne j$，
• 将 $a_i$ 加到 $a_j$ 上，
• 从数组 $a$ 中移除 $a_i$。

注意，经过若干次操作后，$a$ 的元素可以大于 $1$。同时，数组 $a$ 的长度每次操作后会减少 $1$。

你的任务是，最少需要多少次操作，才能使数组 $a$ 非递减，即每个元素都不小于前一个元素？

输入格式

每个测试点包含多组测试用例。第一行包含一个整数 $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$。

输出格式

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

说明/提示

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

在第二个测试用例中，你可以对 $i=1$ 和 $j=5$ 进行一次操作，此时 $a$ 变为 $[0, 0, 1, 2]$，已经是非递减的。

在第三个测试用例中，你可以对 $i=2$ 和 $j=1$ 进行一次操作，此时 $a$ 变为 $[1]$，已经是非递减的。

由 ChatGPT 4.1 翻译

样例

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

0
1
1
3