← 返回题目列表

Codeforces · 2001/A

A. 让一切平等

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

给定一个循环数组 $$$a_1, a_2, \ldots, a_n$$$。

您最多可以对 $$$a$$$ 执行以下操作 $$$n - 1$$$ 次:

- 设$$$m$$$为$$$a$$$的当前大小,可以选择任意两个相邻元素,其中前一个不大于后一个(特别是$$$a_m$$$和$$$a_1$$$相邻,$$$a_m$$$是前一个),并删除其中一个。换句话说,选择一个整数 $$$i$$$ ($$$1 \leq i \leq m$$$),其中 $$$a_i \leq a_{(i \bmod m) + 1}$$$ 成立,并从 $$$a$$$ 中删除 $$$a_i$$$ 或 $$$a_{(i \bmod m) + 1}$$$ 之一。

您的目标是找到使 $$$a$$$ 中的所有元素相等所需的最少操作数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 数组 $$$a$$$ 的元素。

输出

对于每个测试用例,输出一行包含一个整数:使 $$$a$$$ 中的所有元素相等所需的最少操作数。

示例

输入 #1

7
1
1
3
1 2 3
3
1 2 2
5
5 4 3 2 1
6
1 1 2 2 3 3
8
8 7 6 3 8 7 6 3
6
1 1 4 5 1 4

输出 #1

0
2
1
4
4
6
3

注意

在第一个测试用例中,$$$a$$$ 中只有一个元素,因此我们无法进行任何操作。

在第二个测试用例中,我们可以执行以下操作来使$$$a$$$中的所有元素相等:

- 选择$$$i = 2$$$,删除$$$a_3$$$,则$$$a$$$将变为$$$[1, 2]$$$。
- 选择$$$i = 1$$$,删除$$$a_1$$$,则$$$a$$$将变为$$$[2]$$$。

可以证明,我们不能使用少于$$$2$$$的操作使$$$a$$$中的所有元素相等,所以答案是$$$2$$$。