时空限制

1S/512M

题目描述

定义一个数组是“优美的”，当且仅当存在一种对该数组元素的排列方式，使得排列后相邻的两个数字互不相同。

例如，数组 $[1, 1, 2, 3]$ 是优美的，因为它可以被重新排列为 $[1, 2, 1, 3]$，其中没有相邻的数字是相同的。 而数组 $[1, 1, 1, 2]$ 不是优美的，因为无论如何排列，总会有两个 $1$ 相邻。

现在给定一个长度为 $n$ 的数组 $A$，问最少需要从数组中删除多少个数字，才能让剩下的数组变成一个“优美的”数组？

格式

输入格式

本题有多组测试数据。

输入的第一行包含一个整数 $T$，表示测试数据的数量。

对于每个测试数据：第一行包含一个整数 $n$，表示数组的长度。

第二行包含 $n$ 个整数 $A_1, A_2, \ldots, A_n$，表示数组的元素。

输出格式

对于每个测试数据，输出一行，包含一个整数，表示最少需要删除的元素数量。

样例

样例输入 #1

3
6
1 1 1 1 2 3
5
1 1 2 3 4
5
1 1 1 1 1

样例输出 #1

1
0
4

样例解释 #1

对于第一个数据 $[1, 1, 1, 1, 2, 3]$：

• 如果不删除元素，任何排列都会导致两个 $1$ 相邻。
• 如果我们删除一个 $1$，数组变为 $[1, 1, 1, 2, 3]$。它可以被重排为 $[1, 2, 1, 3, 1]$，这是一个优美的数组。
• 故最少需要删除 $1$ 个元素。

对于第二个数据 $[1, 1, 2, 3, 4]$：

• 数组本身就可以被重排为 $[1, 2, 1, 3, 4]$，已经是优美的了。
• 因此，不需要删除任何元素，答案是 $0$。

对于第三个数据 $[1,1,1,1,1]$：

• 数组中只有一种数字 $1$。为了满足条件，我们最多只能留下一个 $1$。
• 故需要删除 $4$ 个 $1$ 来满足条件。

数据规模

对于 $100\%$ 的数据，$1 \leq T \leq 10$，$1 \leq n \leq 10^5$，$1 \leq A_i \leq n$。