F-小苯的极大支配_牛客周赛 Round 119

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 如果一个序列中，存在一个数值 $x$ 使得 $x$ 的出现次数大于其余所有数字的出现次数，则该序列被称为 "支配序列"， $x$ 就被称为这个序列的 "支配数"。例如 $\{1,2,2,3\}$ 就是一个支配序列，此序列中存在数字 $2$ 的出现次数大于其余所有数的出现次数，因此 $2$ 是其的支配数。

$\hspace{15pt}$ 而如果一个 "支配序列" 的 "支配数" 恰好就是该序列的最大值，则序列被称为 "极大支配序列"。

$\hspace{15pt}$ 现在给定一个长度为 $n$ 序列 $a$ ，小苯希望删除 $a$ 中尽可能少的数字（也可以不删），使得剩下的数字构成的序列是一个 "极大支配序列"。你的任务就是求出最少删除的数字个数。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行一个正整数 ，表示序列  的长度。
第二行  个整数 ，表示序列 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据：
输出最少删除的数字个数，以使得剩下的数字序列是一个 "极大支配序列"。

示例1

输入

复制

2
8
1 2 3 2 4 4 3 3
4
1 2 3 4

输出

复制

2
3

说明

对于第一组测试数据，选择删除  即可，剩下的序列为：，其中  是序列的最大值，并且  的出现次数严格大于其余所有数字，因此此序列是一个 "极大支配序列"。