Read problems statements in [Mandarin Chinese], [Russian], and [Bengali] as well.

You are given an array of N integers. Find the *minimum* number of integers you need to delete from the array such that the absolute difference between each pair of integers in the remaining array will become equal.

------ Input Format ------ 

- The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}.

------ Output Format ------ 

For each test case, print a single line containing one integer - the minimum number of integers to be deleted to satisfy the given condition.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
2
1 2
5
2 5 1 2 2
4
1 2 1 2
----- Sample Output 1 ------ 
0
2
2
----- explanation 1 ------ 
Test case $1$: There is only one pair of integers and the absolute difference between them is $|A_{1} - A_{2}| = |1 - 2| = 1$. So there is no need to delete any integer from the given array.

Test case $2$: If the integers $1$ and $5$ are deleted, the array A becomes $[2, 2, 2]$ and the absolute difference between each pair of integers is $0$. There is no possible way to delete less than two integers to satisfy the given condition.

Difficulty: MEDIUM
Tags: Sorting

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
def frequency_check(dictionary):
	for item in range(len(dictionary.keys()) - 1):
		if dictionary.keys()[item] != dictionary.keys()[item + 1]:
			return False
	return True

def max_key(dictionary):
	Max = 0
	for item in dictionary:
		if dictionary[item] > Max:
			Max = dictionary[item]
	return Max

def func():
	n = int(input())
	arr = list(map(int, input().split()))
	if n <= 2:
		return 0
	empt = {}
	for i in range(n):
		if arr[i] not in empt:
			empt[arr[i]] = 1
		else:
			empt[arr[i]] += 1
	if max_key(empt) == 1:
		return n - 2
	return n - max_key(empt)
t = int(input())
while t != 0:
	t = t - 1
	print(func())


from statistics import mode
T = int(input())
while T:
	n = int(input())
	a = list(map(int, input().split()))
	c = mode(a)
	m = a.count(c)
	if n <= 2:
		print(0)
	elif m == 1:
		print(n - 2)
	else:
		print(n - m)
	T = T - 1


t = int(input())
for z in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if n <= 2:
		print(0)
	else:
		max_freq = 0
		freq_map = dict()
		for ele in arr:
			freq_map[ele] = freq_map.get(ele, 0) + 1
			if freq_map[ele] > max_freq:
				max_freq = freq_map[ele]
		if len(freq_map) == n:
			print(n - 2)
		else:
			print(n - max_freq)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		d[i] = d.get(i, 0) + 1
	ans = d[max(d, key=lambda x: d[x])]
	print(n + int(n == 1) - int(ans == 1) - ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n <= 2:
		print(0)
		continue
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] = d[i] + 1
	z = max(d.values())
	if z == 1:
		print(n - 2)
	else:
		print(n - z)


from collections import Counter
n = int(input())
for i in range(n):
	a = int(input())
	l = list(map(int, input().split()))
	x = max(Counter(l).values())
	if a <= 2:
		print('0')
	elif x == 1:
		print(a - 2)
	elif x > 1:
		print(a - x)


test_cases = int(input())
list_final = []
for t in range(test_cases):
	n = int(input())
	data = input()
	if n > 2:
		list_data = []
		a = 0
		for j in range(len(data)):
			if data[j] == ' ':
				list_data.append(data[a:j])
				a = j + 1
		list_data.append(data[a:])
		list_data.sort()
		list_count = []
		count = 1
		for k in range(1, n):
			if list_data[k] == list_data[k - 1]:
				count = count + 1
			else:
				list_count.append(count)
				count = 1
		list_count.append(count)
		max_count = int(list_count[0])
		for i in range(len(list_count)):
			if int(list_count[i]) > max_count:
				max_count = int(list_count[i])
		if len(list_count) != n:
			req_ans = n - max_count
			list_final.append(req_ans)
		else:
			list_final.append(n - 2)
	else:
		list_final.append(0)
for k in range(len(list_final)):
	print(list_final[k])


T: int = int(input())
for x in range(T):
	N: int = int(input())
	inp: list = list(map(int, input().split(' ')))
	count: dict = {}
	if len(inp) <= 2:
		print(0)
	else:
		for i in range(0, N):
			n = inp[i]
			if n in count:
				k = count[n] + 1
				count.update({n: k})
			else:
				count[n] = 1
		maxcount: int = max(count.values())
		if maxcount == 1:
			print(N - 2)
		else:
			print(N - maxcount)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for i in arr:
		d[i] = d.get(i, 0) + 1
	odd_count = 0
	even_count = 0
	m = max(d.values())
	if n <= 2:
		print('0')
	elif m == 1:
		print(n - 2)
	elif m > 1:
		print(n - m)


from statistics import mode
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	r = mode(a)
	fre = a.count(r)
	if n <= 2:
		print(0)
	elif fre == 1:
		print(n - 2)
	else:
		print(n - fre)
	t = t - 1


from statistics import mode

def grab_input():
	N = int(input())
	A = list(map(int, input().split()))
	return (N, A)
T = int(input())
while T > 0:
	(N, A) = grab_input()
	m = mode(A)
	freq = A.count(m)
	if N <= 2:
		print('0')
	elif freq == 1:
		print(N - 2)
	else:
		print(N - freq)
	T -= 1


for temp in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	freq = {}
	for i in arr:
		try:
			freq[i] += 1
		except:
			freq[i] = 1
	m1 = 0
	l = len(freq)
	if n <= 2:
		print(0)
	elif n == 3:
		if l == 1:
			print(0)
		else:
			print(1)
	else:
		for j in freq.values():
			if j > m1:
				m1 = j
		if m1 == 1:
			print(n - 2)
		else:
			print(n - m1)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n <= 2:
		print(n - n)
		continue
	freq = defaultdict(int)
	for num in arr:
		freq[num] += 1
	a = sorted(freq.items(), key=lambda x: x[1])[-1]
	if a[1] == 1:
		print(n - 2)
	else:
		print(n - a[1])


from statistics import mode
k = int(input())
for _ in range(k):
	n = int(input())
	arr = list(map(int, input().split()))
	p = mode(arr)
	s = arr.count(p)
	if n <= 2:
		print(0)
	elif s == 1:
		print(n - 2)
	else:
		print(n - s)


for _ in range(int(input())):
	n = int(input())
	lst = [int(x) for x in input().split()]
	if len(lst) > 2:
		counts = {}
		for item in lst:
			if item in counts:
				counts[item] += 1
			else:
				counts[item] = 1
		max_count = 0
		max_item = None
		for (item, count) in counts.items():
			if count > max_count:
				max_count = count
				max_item = item
		if max_count == 1:
			print(len(lst) - 2)
		else:
			print(len(lst) - max_count)
	else:
		print(0)


from statistics import mode
n = int(input())
for t in range(n):
	n = int(input())
	A = [int(a) for a in input().split()]
	c = mode(A)
	m = A.count(c)
	if n <= 2:
		print(0)
	elif m == 1:
		print(n - 2)
	else:
		print(n - m)


t = int(input())
for _ in range(t):
	n = int(input())
	numbers = list(map(int, input().split()))
	numbers.sort()
	max_occuring_number = None
	current_num_occurence = 0
	max_occurence = None
	last_number = None
	for (index, number) in enumerate(numbers):
		if index == 0:
			last_number = number
			num_count = 1
			max_occurence = 1
			continue
		if number == last_number:
			num_count += 1
		else:
			if num_count > max_occurence:
				max_occurence = num_count
			num_count = 1
		last_number = number
	if num_count > max_occurence:
		max_occurence = num_count
	if n == 2 and max_occurence == 1:
		print(0)
	elif max_occurence == 1 and n > 1:
		print(n - max_occurence - 1)
	else:
		print(n - max_occurence)


import statistics
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = statistics.mode(a)
	y = a.count(x)
	if n <= 2:
		print(0)
	elif y == 1:
		print(n - 2)
	else:
		print(n - y)


get_int = lambda : int(input())
get_mint = lambda : list(map(int, input().split()))
for _ in range(get_int()):
	N = get_int()
	A = get_mint()
	if N < 3:
		print(0)
		continue
	if len(set(A)) == N:
		print(N - 2)
		continue
	d = dict()
	for Ai in A:
		if Ai not in d:
			d[Ai] = 0
		d[Ai] += 1
	print(N - max([v for v in d.values()]))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n <= 2:
		print(0)
		continue
	from statistics import mode
	f = arr.count(mode(arr))
	if f != 1:
		print(n - f)
	else:
		print(n - 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	m = [0, 0]
	for i in a:
		d.setdefault(i, 0)
		d[i] += 1
		if d[i] > m[0]:
			m[0] = d[i]
			m[1] = i
	if n < 3:
		print(0)
	elif m[0] == 1:
		print(n - 2)
	else:
		print(n - m[0])


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = defaultdict(int)
	q = 0
	for i in l:
		d[i] += 1
		if d[i] > q:
			q = d[i]
	if n == 2 or n == 1 or q == n:
		print(0)
	elif q == 1:
		print(n - 2)
	else:
		print(n - q)


from statistics import mode
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	c = mode(A)
	m = A.count(c)
	if n <= 2:
		print(0)
	elif m == 1:
		print(n - 2)
	else:
		print(n - m)


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n <= 2:
		print(0)
	else:
		s = set(arr)
		set_len = len(s)
		if n == set_len:
			print(n - 2)
		else:
			c = Counter(arr)
			m = max(c.values())
			print(n - m)


def min_deletions(arr):
	freq = {}
	for num in arr:
		freq[num] = freq.get(num, 0) + 1
	max_freq = max(freq.values())
	if max_freq == len(arr):
		return 0
	if max_freq == 1:
		return len(arr) - 2
	return len(arr) - max_freq
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(min_deletions(arr))


from collections import Counter
t = int(input())
list_input = []
for i in range(t):
	n = int(input())
	list1 = list(map(int, input().split(' ')))
	list_input.append([n, list1])
for i in range(t):
	ele_count = Counter(list_input[i][1])
	val = max(ele_count.values())
	length = len(list_input[i][1])
	if val == 1 and length == 1:
		print(0)
	elif val == 1 and length > 1:
		print(length - 2)
	else:
		print(length - val)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	if n <= 2:
		print(0)
	else:
		d = {}
		x = 0
		for i in range(n):
			d[a[i]] = d.get(a[i], 0) + 1
		for i in d.values():
			if i > x:
				x = i
		if x == 1:
			print(n - 2)
		else:
			print(n - x)
	t = t - 1


def solve(array):
	if len(array) <= 2:
		return 0
	max_count = 0
	hashing = {}
	for x in array:
		try:
			hashing[x] += 1
		except:
			hashing[x] = 1
		if hashing[x] > max_count:
			max_count = hashing[x]
	if max_count == 1:
		return len(array) - 2
	return len(array) - max_count
test = int(input())
for _ in range(test):
	x = int(input())
	array = [int(x) for x in input().split()]
	print(solve(array))


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n <= 2:
		print(0)
	else:
		d = {}
		for i in range(n):
			d[a[i]] = d.get(a[i], 0) + 1
		v = list(d.values())
		m = 0
		for i in v:
			if i > m:
				m = i
		if m == 1:
			print(n - 2)
		else:
			print(n - m)


from os import path
import sys
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	if len(list(set(a))) == 1:
		print(0)
	else:
		mx = max(c.values())
		if mx > 1:
			print(n - mx)
		elif mx == 1:
			print(n - 2)


import statistics
for t in range(int(input())):
	l = int(input())
	n = list(map(int, input().split()))
	if l <= 2:
		print(0)
	else:
		rep = n.count(statistics.mode(n))
		if rep == 1:
			print(l - 2)
		else:
			print(l - rep)


from collections import Counter
t = int(input())
for z in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = dict(Counter(l))
	ct = max(d.values())
	if n <= 2:
		print(0)
	elif ct == 1:
		print(n - 2)
	else:
		print(n - ct)


from collections import Counter
T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	ct = 0
	if n <= 2:
		print(0)
	else:
		d = dict(Counter(a))
		ct = max(d.values())
		if ct == 1:
			print(n - 2)
		else:
			print(n - ct)


import statistics
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n <= 2:
		print(0)
	else:
		m = statistics.mode(l)
		if l.count(m) > 1:
			print(n - l.count(m))
		else:
			print(n - 2)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 2 or n == 1:
		print(0)
	else:
		dic = {}
		for i in a:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		maxi = max(dic.values())
		sumi = sum(dic.values())
		if maxi == 1:
			print(n - 2)
		else:
			print(sumi - maxi)


from statistics import mode
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	res = mode(l)
	if n <= 2:
		print(0)
	elif l.count(res) > 1:
		print(n - l.count(res))
	else:
		print(n - 2)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	a = Counter(map(int, input().split()))
	if n < 3:
		print(0)
		continue
	print(min(n - max(a.values()), n - 2))


test = int(input())
for z in range(test):
	n = int(input())
	A = list(map(int, input().split()))
	if n <= 2:
		print(0)
		continue
	d = {}
	Max = 1
	for i in A:
		if i in d:
			d[i] += 1
			if Max < d[i]:
				Max = d[i]
		else:
			d[i] = 1
	if Max == 1:
		print(n - 2)
	else:
		print(n - Max)


for _ in range(int(input())):
	numofp = int(input())
	arr = list(map(int, input().split()))
	setr = {}
	for i in range(numofp):
		mur = arr[i]
		if mur in setr:
			setr[mur] += 1
		else:
			setr[mur] = 1
	kon = max(setr, key=lambda x: setr[x])
	if numofp <= 2:
		print(0)
	elif setr[kon] == 1:
		print(numofp - 2)
	else:
		print(numofp - setr[kon])


t = int(input())
for _ in range(t):
	n = int(input())
	val = input().split()
	dict = {}
	greatest = 0
	for i in val:
		if i in dict:
			dict[i] = dict[i] + 1
		else:
			dict[i] = 1
		greatest = max(dict[i], greatest)
	if greatest > 2:
		print(n - greatest)
	else:
		print(max(0, n - 2))


from statistics import mode
t = int(input())
for i in range(t):
	a = int(input())
	b = list(map(int, input().split()))
	c = mode(b)
	d = b.count(c)
	if len(b) <= 2:
		print(0)
	elif d == 1:
		print(a - 2)
	else:
		print(a - d)


for i in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	if n <= 2:
		print(0)
	else:
		counter = {}
		for i in array:
			if i in counter.keys():
				counter[i] += 1
			else:
				counter[i] = 1
		max_ = max(counter.values())
		if max_ == 1:
			print(n - 2)
		else:
			print(n - max_)


def sol():
	a = int(input())
	b = list(map(int, input().split()))
	if a < 3:
		return 0
	else:
		z = {}
		for i in b:
			if i in z:
				z[i] += 1
			else:
				z[i] = 1
		y = max(z.values())
		if y == 1:
			return a - 2
		else:
			return a - max(z.values())
n = int(input())
for _ in range(n):
	print(sol())


from statistics import mode
t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))[:n]
	m = 0
	if n <= 2:
		print('0')
	else:
		m = l.count(mode(l))
		print(n - m) if m > 1 else print(n - 2)
	t -= 1


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = Counter(arr)
	if n == 1 or n == 2:
		print(0)
	else:
		print(min(n - max(cnt.values()), n - 2))


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	freq = {}
	for i in arr:
		if i in freq:
			freq[i] += 1
		else:
			freq[i] = 1
	maxi = 0
	for i in freq:
		maxi = max(maxi, freq[i])
	if n == 1 or n == 2:
		print(0)
	elif maxi == 1:
		print(n - 2)
	else:
		print(n - maxi)


for na in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	if n <= 2:
		print(0)
	elif n == len(s):
		print(n - 2)
	else:
		x = {}
		for i in l:
			if i in x:
				x[i] += 1
			else:
				x[i] = 1
		maxi = 0
		for i in x:
			maxi = max(maxi, x[i])
		print(n - maxi)


import collections

def calc_min_deletion(A, n):
	if n <= 2:
		return 0
	c = collections.Counter(A)
	return min(n - c.most_common(1)[0][1], n - 2)
for _ in range(int(input())):
	n = int(input())
	A = [int(x) for x in input().split()]
	print(calc_min_deletion(A, n))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n <= 2:
		print(0)
	elif len(set(arr)) == len(arr):
		print(n - 2)
	else:
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		m = 0
		for i in d:
			m = max(m, d[i])
		print(n - m)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(k) for k in input().split()]
	a.sort()
	m = 2
	c = 0
	ox = 0
	for x in a:
		if x == ox:
			c += 1
			if c > m:
				m = c
		else:
			c = 1
		ox = x
	if n > 1:
		print(n - m)
	else:
		print(0)


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	counts = Counter(arr)
	if n <= 2:
		print(0)
	else:
		print(n - max(2, max(counts.values())))


from collections import Counter
for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	c = Counter(x)
	s = max(c.values())
	print(max(min(n - s, n - 2), 0))


import sys, collections
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n <= 2:
		print(0)
		continue
	freq = collections.Counter(a)
	ans = n - max(2, max(freq.values()))
	print(ans)


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	d = {}
	if a > 2:
		for i in range(a):
			if l[i] not in d:
				d[l[i]] = 0
			d[l[i]] += 1
		fre = list(d.values())
		m = max(fre)
		if m == 1:
			print(a - 2)
		else:
			print(a - m)
	else:
		print(0)


for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	if N <= 2:
		print(0)
	else:
		dc = {}
		max = 1
		for i in range(N):
			dc[A[i]] = 0
		for i in range(N):
			dc[A[i]] += 1
		for i in dc:
			if dc[i] > max:
				max = dc[i]
		if max > 2:
			print(N - max)
		else:
			print(N - 2)


import collections
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = collections.defaultdict(lambda : 0)
	if n <= 2:
		print('0')
	else:
		mx = 0
		for x in a:
			d[x] += 1
			mx = max(mx, d[x])
		if mx == 1:
			print(n - 2)
		else:
			print(n - mx)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if n <= 2:
		print(0)
	else:
		data = Counter(arr)
		ma = data.most_common(1)[0][1]
		if ma > 2:
			print(n - ma)
		else:
			print(n - 2)


from collections import Counter
for temp in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if n <= 2:
		print(0)
	else:
		data = Counter(arr)
		max_freq = data.most_common(1)[0][1]
		if max_freq > 2:
			print(n - max_freq)
		else:
			print(n - 2)


for i in range(int(input())):
	n = int(input())
	lis = list(map(int, input().strip().split(' ')))
	lis.sort()
	a = []
	if n == 2 or n == 1:
		print(0)
	else:
		while lis:
			x = 0
			s = lis[0]
			while lis and s == lis[0]:
				x += 1
				lis.pop(0)
			a.append(x)
		a.sort()
		if a[-1] != 1:
			print(n - a[-1])
		else:
			print(n - 2)


T = int(input())
while T > 0:
	n = int(input())
	a = list(map(int, input().split()[:n]))
	dict = {}
	for i in range(n):
		if a[i] in dict:
			dict[a[i]] += 1
		else:
			dict[a[i]] = 1
	l = []
	for i in dict:
		l.append(dict[i])
	l.sort()
	if len(l) == n:
		if len(l) > 1:
			print(n - 2)
		else:
			print(0)
	else:
		print(n - l[-1])
	T -= 1


t = int(input())
from collections import Counter
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	col = Counter(lst)
	if len(col) == len(lst):
		if n > 1:
			print(n - 2)
		else:
			print(0)
	else:
		mx = 0
		for i in col:
			val = col[i]
			mx = max(val, mx)
		print(n - mx)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	s = set(l)
	if n <= 2:
		print(0)
	else:
		d = Counter(l)
		res = 0
		f = 0
		m = max(d.values())
		if m == 1:
			print(n - 2)
		else:
			print(n - m)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	nc = {}
	count = 0
	if n <= 2:
		print(0)
		continue
	for i in lst:
		c = nc.get(i, 0) + 1
		count = max(c, count)
		nc[i] = nc.get(i, 0) + 1
	if count == 1:
		count += 1
	print(n - count)


repeats = int(input())
for _ in range(0, repeats):
	input()
	nums = list(map(int, input().split()))
	if len(nums) <= 2:
		print(0)
		continue
	nc = {}
	count_max = 0
	for n in nums:
		c = nc.get(n, 0) + 1
		count_max = max(c, count_max)
		nc[n] = nc.get(n, 0) + 1
	if count_max == 1:
		count_max += 1
	print(len(nums) - count_max)


t = int(input())
for _ in range(t):
	N = int(input())
	A = input().split()
	unique = {}
	if N <= 2:
		print(0)
		continue
	maxi_nb = 0
	for i in A:
		if i in unique:
			unique[i] = unique[i] + 1
		else:
			unique[i] = 1
		if unique[i] > maxi_nb:
			maxi_nb = unique[i]
	if maxi_nb >= 2:
		print(N - maxi_nb)
	else:
		print(N - 2)


import sys
t = int(input())
for i in range(t):
	while t > 0:
		n = int(input())
		l1 = list(map(int, input().split()))
		l = len(l1)
		d = {}
		m = 0
		if l <= 2:
			print(0)
		else:
			for i in l1:
				if i not in d:
					d[i] = 1
				else:
					d[i] += 1
				m = max(m, d[i])
			if m == 1:
				print(l - 2)
			else:
				print(l - m)
		t -= 1


test_cases = int(input())
for i in range(test_cases):
	num_integers = int(input())
	arr = [int(x) for x in input().split()]
	frequency = {}
	for i in range(num_integers):
		if arr[i] not in frequency:
			frequency[arr[i]] = 1
		else:
			frequency[arr[i]] += 1
	if num_integers == 1 or num_integers == 2:
		print('0')
	else:
		max_frequency = 0
		for i in frequency.values():
			max_frequency = max(max_frequency, i)
		if max_frequency == 1:
			max_frequency += 1
		print(num_integers - max_frequency)


import statistics
T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	if n > 2:
		b = a.count(statistics.mode(a))
		if b == 1:
			print(n - 2)
		else:
			print(n - b)
	else:
		print(0)


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	nums = list(map(int, input().split()))
	mp = {}
	mx = 0
	for j in range(n):
		x = nums[j]
		if x not in mp:
			mp[x] = 1
		else:
			mp[x] += 1
		mx = max(mx, mp[x])
	if n <= 2:
		print(0)
	else:
		print(min(n - 2, n - mx))


import sys
from collections import deque
import math
t = int(input())
for i in range(t):
	while t > 0:
		n = int(input())
		arr = list(map(int, input().split()))
		l = len(arr)
		dict = {}
		maxi = 0
		if l == 1 or l == 2:
			print(0)
		else:
			for i in arr:
				if i not in dict:
					dict[i] = 1
				else:
					dict[i] += 1
				maxi = max(maxi, dict[i])
			if maxi == 1:
				print(l - 2)
			else:
				print(l - maxi)
		t -= 1