Rebellion

题意翻译

给定长度为 $n$ 的只包含 $0$ 和 $1$ 的序列 $a$，每次操作可以选择两个下标 $i$ 和 $j$，将 $a_j$ 加上 $a_i$ 并将 $a_i$ 删除。求最小的操作次数使得 $a$ 成为一个不降序列。 注意操作之后 $a$ 中的数可能大于 $1$。

题目描述

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?

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #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

说明

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.

**反叛**

**题意翻译**
给定一个长度为 $ n $ 的只包含 $ 0 $ 和 $ 1 $ 的序列 $ a $，每次操作可以选择两个下标 $ i $ 和 $ j $，将 $ a_j $ 加上 $ a_i $ 并将 $ a_i $ 删除。求最小的操作次数使得 $ a $ 成为一个不降序列。注意操作之后 $ a $ 中的数可能大于 $ 1 $。

**题目描述**
你有大小为 $ n $ 的数组 $ a $，它只包含零和一。你可以进行以下操作：
- 选择两个索引 $ 1 \le i , j \le n $，$ i \ne j $，
- 将 $ a_i $ 加到 $ a_j $ 上，
- 从 $ a $ 中移除 $ a_i $。

注意，在进行一些操作后，$ a $ 中的元素可能变得大于 $ 1 $。还要注意，操作后 $ n $ 会减少 $ 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 $ 成为非降序所需的最小操作次数。

**输入输出样例**
**输入样例 #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] $ 并成为非降序。**反叛** **题意翻译** 给定一个长度为 $ n $ 的只包含 $ 0 $ 和 $ 1 $ 的序列 $ a $，每次操作可以选择两个下标 $ i $ 和 $ j $，将 $ a_j $ 加上 $ a_i $ 并将 $ a_i $ 删除。求最小的操作次数使得 $ a $ 成为一个不降序列。注意操作之后 $ a $ 中的数可能大于 $ 1 $。 **题目描述** 你有大小为 $ n $ 的数组 $ a $，它只包含零和一。你可以进行以下操作： - 选择两个索引 $ 1 \le i , j \le n $，$ i \ne j $， - 将 $ a_i $ 加到 $ a_j $ 上， - 从 $ a $ 中移除 $ a_i $。 注意，在进行一些操作后，$ a $ 中的元素可能变得大于 $ 1 $。还要注意，操作后 $ n $ 会减少 $ 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 $ 成为非降序所需的最小操作次数。 **输入输出样例** **输入样例 #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] $ 并成为非降序。