您有一个大小为 $$$n$$$ 的数组 $$$a$$$,仅由零和一组成。您可以进行以下操作:
- 选择两个索引 $$$1 \le i , j \le n$$$, $$$i \ne j$$$,
- 将 $$$a_{i}$$$ 添加到 $$$a_{j}$$$,
- 从 $$$a$$$ 中删除 $$$a_{i}$$$。
请注意,执行某些操作后,$$$a$$$ 的元素可能会变得大于 $$$1$$$。另请注意,操作后 $$$n$$$ 会减少 $$$1$$$。
使 $$$a$$$ 非递减所需的最少操作次数是多少,i。 e.每个元素不小于前一个元素?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 非递减所需的最小操作数。
示例
输入 #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
输出 #1
0 1 1 3
注意
在第一个测试用例中,$$$a$$$已经是非递减的,所以你不需要做任何操作,答案是$$$0$$$。
在第二个测试用例中,您可以对 $$$i = 1$$$ 和 $$$j = 5$$$ 执行操作,因此 $$$a$$$ 将等于 $$$[0, 0, 1, 2]$$$ 并且变为非递减。
在第三个测试用例中,您可以对 $$$i = 2$$$ 和 $$$j = 1$$$ 执行操作,因此 $$$a$$$ 将等于 $$$[1]$$$ 并且变为非减。