题目描述

研究蘑菇的专家安德鲁在研究新加坡的本地蘑菇。

作为研究的一部分，安德鲁采集了 $n$ 个蘑菇，编号为 $0$ 到 $n-1$。每个蘑菇均为两种蘑菇种类之⼀，称为 $A$ 或 $B$。

安德鲁知道 蘑菇 $0$ 属于种类 $A$, 但是由于这两种蘑菇看起来很相似，他不知道蘑菇 $1$ 到 $n-1$ 属于哪一种。

幸运的是，安德鲁的实验室里有一台机器可以帮助他。在使用这台机器时，需要将两个或者多个蘑菇放到机器里，并摆成一排（以任意顺序），然后打开机器。接下来，这台机器会计算所有不属于同一种类的 相邻 蘑菇对的个数。例如，如果你把种类为 $[A,B,B,A]$ 的蘑菇（按照这个顺序）放到机器中，结果应该是 $2$。

但是，因为机器操作非常昂贵，机器只能使用有限的次数。此外，在机器的所有使用中，放置到机器中的蘑菇总数不能超过 $10^5$。请使用这台机器帮助安德鲁来数一数他采集了多少个种类为 $A$ 的蘑菇。

实现细节

你需要实现以下函数：

int count_mushrooms(int n)

• $n$: 安德鲁采集到的蘑菇数量。
• 该函数应该被调用恰好一次，而且要返回种类为 $A$ 的蘑菇的个数。

以上函数可以调用以下函数：

int use_machine(int[] x)

• $x$: 一个长度介于 $2$ 和 $n$ 的数组（包括 $2$ 和 $n$)，按顺序给出放在机器中的蘑菇的编号。
• $x$ 的元素必须是在 $0$ 到 $n-1$ 之间（包括 $0$ 和 $n-1$) 互不相同 的整数。
• 假设数组 $x$ 的长度为 $d$。那么，此函数返回不同的下标 $j$ 的个数，满足 $0 \le j \le d-2$ 并且 $x[j]$ 和 $x[j+1]$ 属于不同种类。
• 该函数最多可以被调用 $2 \times 10^4$ 次。
• 在对函数 use_machine 的所有调用中，所有被传到该函数 use_machine 的 $x$ 的总长度不能超过 $10^5$。

提示

样例说明

例 1

考虑以下场景：有 $3$ 个蘑菇，种类依次为 $[A,B,B]$。函数 count_mushrooms 用以下方式调用

count_mushrooms(3)

该函数可以调用 use_machine([0, 1, 2])，在该场景下调用返回 $1$。 函数接着调用 use_machine([2, 1])，该调用返回 $0$。

此时，已经有足够的信息来推出只有 $1$ 个 $A$ 类蘑菇。所以，函数 count_mushrooms 应该返回 $1$。

例 2

考虑一个例子：有 $4$ 个蘑菇，种类依次为 $[A,B,A,A]$。函数 count_mushrooms 被调用如下：

count_mushrooms(4)

该函数可以调用 use_machine([0, 2, 1, 3])，该调用返回 $2$。接着调用 use_machine([1,2])，该调用返回 $1$。

此时，已有足够的信息推出：有 $3$ 个 $A$ 类蘑菇。因此，函数 count_mushrooms 应该返回 $3$。

约束条件

• $2 \le n \le 2 \times 10^4$

计分

在所有测试用例中，如果对函数 use_machine 的调用不符合上面所述的要求，或者 count_mushrooms 的返回值不正确，你的解答得分将为 $0$。否则，令 $Q$ 为所有测试样例中对函数 use_machine 的最大调用次数。那么，得分将按照以下表格进行计算：

条件	得分
$2 \times 10^4 \le Q$	$0$
$10010 < Q \le 2 \times 10^4$	$10$
$904 < Q \le 10010$	$25$
$226 < Q \le 904$	$\frac{226}{Q} \cdot 100$
$Q \le 226$	$100$

在有些测试用例上，评测程序的行为是自适应的。也就是说，在这些测试用例中，评测程序并没有一个固定的蘑菇种类序列。相反，评测程序中所给出的回答可能依赖于此前对 use_machine 的调用。

但是可以保证，评测程序中所给出的回答满足：在每次交互之后，至少存在一个蘑菇种类序列，它能够与当前所给出过的所有回答都相符。

评测程序示例

评测程序示例读入一个整数数组 $s$，该数组给出了蘑菇的种类。对于所有 $0 \le i \le n-1$，$s[i]=0$ 表示蘑菇 $i$ 的种类是 $A$，$s[i]=1$ 表示蘑菇 $i$ 的种类是 $B$。评测程序示例读取如下格式的输入数据：

第 $1$ 行: $n$
第 $2$ 行: $s[0]\ s[1]\ \ldots\ s[n-1]$

评测程序示例的输出为如下格式：

第 $1$ 行: count_mushrooms 的返回值。
第 $2$ 行: 调用 use_machine 的次数。

注意评测程序示例不是自适应的。