← 返回题目列表

Codeforces · 1746/B

B. 叛乱

中文机器翻译题面 查看原题

您有一个大小为 $$$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]$$$ 并且变为非减。