Read problem statements in [Mandarin Chinese] and [Russian].

Chef opted for Bio-Statistics as an Open-Elective course in his university, but soon got bored, and decided to text his friends during lectures. The instructor caught Chef, and decided to punish him, by giving him a special assignment.

There are $N$ numbers in a list $A = A_{1}, A_{2}, \ldots, A_{N}$. Chef needs to find the [mode] of the frequencies of the numbers. If there are multiple modal values, report the smallest one. In other words, find the frequency of all the numbers, and then find the frequency which has the highest frequency. If multiple such frequencies exist, report the smallest (non-zero) one.

More formally, for every $v$ such that there exists at least one $i$ such that $A_{i} = v$, find the number of $j$ such that $A_{j} = v$, and call that the frequency of $v$, denoted by $freq(v)$. Then find the value $w$ such that $freq(v) = w$ for the most number of $v$s considered in the previous step. If there are multiple values $w$ which satisfy this, output the smallest among them.

As you are one of Chef's friends, help him complete the assignment.

------ Input: ------

The first line contains an integer $T$, the number of test cases. 
The first line of each test case contains an integer $N$, the number of values in Chef's assignment.
The second line of each test case contains $N$ space-separated integers, $A_{i}$, denoting the values in Chef's assignment. 

------ Output: ------
For each test case, print the mode of the frequencies of the numbers, in a new line. 

------ Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10000$
$1 ≤ A_{i} ≤ 10$

------ Subtasks ------
30 points : $1 ≤ N ≤ 100$
70 points : Original constraints.

----- Sample Input 1 ------ 
2

8

5 9 2 9 7 2 5 3

9

5 9 2 9 7 2 5 3 1
----- Sample Output 1 ------ 
2

1
----- explanation 1 ------ 
- Test case 1: $(2$, $9$ and $5)$ have frequency $2$, while $(3$ and $7)$ have frequency $1$. Three numbers have frequency $2$, while $2$ numbers have frequency $1$. Thus, the mode of the frequencies is $2$.

- Test case 2: $(2$, $9$ and $5)$ have frequency $2$, while $(3$, $1$ and $7)$ have frequency $1$. Three numbers have frequency $2$, and $3$ numbers have frequency $1$. Since there are two modal values $1$ and $2$, we report the smaller one: $1$.

Source: codechef | Difficulty: EASY
Tags: Data structures

Implementation


Solutions:
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = list(Counter(a).values())
	b = Counter(a)
	v = []
	k = list(b.keys())
	k.sort()
	for i in range(len(k)):
		v.append(b[k[i]])
	print(k[v.index(max(v))])


from collections import Counter

def check(a, b):
	t = []
	for i in a:
		if a[i] == b:
			t.append(i)
	return min(t)
for tc in range(int(input())):
	n = int(input())
	l = map(int, input().split())
	x = Counter(l)
	y = Counter(x.values())
	z = max(y.values())
	print(check(y, z))


import math
for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	d = {}
	for i in range(N):
		if L[i] not in d.keys():
			d[L[i]] = 1
		else:
			d[L[i]] += 1
	L1 = list(d.values())
	L2 = list(set(d.values()))
	max = 0
	res = math.inf
	for i in range(len(L2)):
		if L1.count(L2[i]) == max:
			if L2[i] < res:
				res = L2[i]
		elif L1.count(L2[i]) > max:
			max = L1.count(L2[i])
			res = L2[i]
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(dt, dt1) = ({}, {})
	for i in a:
		dt[i] = dt.get(i, 0) + 1
	for i in dt.values():
		dt1[i] = dt1.get(i, 0) + 1
	m = max(dt1.values())
	l = []
	for (key, values) in dt1.items():
		if values == m:
			l.append(key)
	print(min(l))


import os, sys, io, math
from re import *
from math import *
from array import *
from heapq import *
from bisect import *
from functools import *
from itertools import *
from statistics import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IP = lambda : map(int, input().split())
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())

def f():
	(n, l) = (IN(), I())
	d = Counter(l)
	r = {}
	for i in d:
		if d[i] in r:
			r[d[i]] += 1
		else:
			r[d[i]] = 1
	res = 99999999
	c = -999999999
	for i in r:
		if r[i] > c:
			c = r[i]
	for i in r:
		if r[i] == c:
			res = min(res, i)
	return res
for _ in range(IN()):
	print(f())


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	s = list(set(l))
	for i in s:
		l1.append(l.count(i))
	l2 = list(set(l1))
	l2.sort()
	m = 0
	for i in l2:
		if l1.count(i) > l1.count(m):
			m = i
	print(m)


t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	B = sorted(set(A))
	P = []
	for i in B:
		c = A.count(i)
		P.append(c)
	P = sorted(P)
	max = 0
	res = P[0]
	for j in P:
		freq = P.count(j)
		if freq > max:
			max = freq
			res = j
	print(res)


for i in range(int(input())):
	n = int(input())
	lt = list(map(int, input().split()))
	s = set(lt)
	lt1 = []
	for y in s:
		lt1.append(lt.count(y))
	s2 = set(lt1)
	d = {}
	for p in s2:
		d[p] = lt1.count(p)
	mc = 0
	cn = 999999999999999
	for x in d:
		if d[x] > mc:
			mc = d[x]
			cn = x
		elif d[x] == mc and x < cn:
			cn = x
	print(cn)


from collections import Counter
for i in range(0, int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = Counter(a)
	l = []
	for j in d:
		l.append(d[j])
	s = Counter(l)
	k = 0
	d = n
	for h in s:
		if s[h] > k:
			k = s[h]
			d = h
		elif s[h] == k:
			k = s[h]
			if d > h:
				d = h
			else:
				d = d
		else:
			continue
	print(d)


from collections import Counter
for _ in range(int(input())):
	s = int(input())
	l = list(map(int, input().split()))
	dic = Counter(l)
	dic2 = {}
	for (i, j) in dic.items():
		if j in dic2:
			dic2[j] += 1
		else:
			dic2[j] = 1
	m = max(dic2.values())
	maxi = float('inf')
	for (i, j) in dic2.items():
		if j == m:
			maxi = min(maxi, i)
	print(maxi)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = []
	for i in set(l):
		p.append(l.count(i))
	s = sorted(list(set(p)))
	w = []
	for i in s:
		w.append(p.count(i))
	m = w[0]
	res = s[0]
	for i in range(len(w)):
		if m < w[i]:
			m = w[i]
			res = s[i]
	print(res)


for i in range(int(input())):
	n = int(input())
	ol = list(map(int, input().split()))
	d = {}
	for i in ol:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	f = sorted(d.values())
	d = {}
	s1 = sorted(set(f))
	for i in f:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	ff = list(d.values())
	m = ff[0]
	res = s1[0]
	for i in range(len(ff)):
		if m < ff[i]:
			m = ff[i]
			res = s1[i]
	print(res)


for i in range(int(input())):
	n = int(input())
	ol = list(map(int, input().split()))
	s1 = set(ol)
	f = []
	for i in s1:
		f.append(ol.count(i))
	s2 = sorted(set(f))
	ff = []
	for i in s2:
		ff.append(f.count(i))
	m = ff[0]
	res = s2[0]
	for i in range(len(ff)):
		if m < ff[i]:
			m = ff[i]
			res = s2[i]
	print(res)


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = sorted(set(a))
	p = []
	d = []
	for j in c:
		s = a.count(j)
		p.append(s)
	p.sort()
	m = 0
	r = p[0]
	for j in p:
		f = p.count(j)
		if f > m:
			m = f
			r = j
	print(r)


def find_mod(n, arr):
	fre = dict()
	fre_fre_dic = dict()
	for ele in arr:
		fre[ele] = fre.get(ele, 0) + 1
	new_arr = fre.values()
	for ele in new_arr:
		fre_fre_dic[ele] = fre_fre_dic.get(ele, 0) + 1
	mx = 0
	for (k, v) in fre_fre_dic.items():
		if v >= mx:
			if v > mx:
				mx = v
				ans = k
			if v == mx and k < ans:
				ans = k
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = find_mod(n, arr)
	print(ans)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ob = Counter(l)
	v = ob.values()
	ob1 = Counter(v)
	ch = float('inf')
	m = max(ob1.values())
	for (x, y) in ob1.items():
		if y == m:
			ch = min(ch, x)
	print(ch)


from collections import Counter as C
import statistics as S
for _ in range(int(input())):
	n = int(input())
	print(min(S.multimode(C(list(map(int, input().split(' ')))).values())))


from collections import Counter
import statistics
for _ in range(int(input())):
	mean = []
	n = int(input())
	numbers = list(map(int, input().split()))
	dic = Counter(numbers)
	var = dic.values()
	var1 = statistics.multimode(var)
	print(min(var1))


from collections import Counter
import statistics
t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	c = Counter(b)
	ckey = c.values()
	cmode = statistics.multimode(ckey)
	print(min(cmode))


from collections import Counter
t = int(input())
for _ in range(t):
	size = int(input())
	num = input()
	num = num.split()
	ans = []
	c = Counter(num)
	for (key, value) in c.items():
		ans.append(value)
	c1 = Counter(ans)
	c1 = sorted(c1.items(), key=lambda x: (-x[1], x[0]))
	print(c1[0][0])


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(d, v) = ({}, {})
	s = []
	for k in a:
		if k not in d:
			d[k] = 1
		else:
			d[k] += 1
	for i in d.values():
		if i not in v:
			v[i] = 1
		else:
			v[i] += 1
	m = max(v.values())
	for (k1, v1) in v.items():
		if v[k1] == m:
			s.append(k1)
	s.sort()
	print(s[0])


from collections import Counter
import statistics
for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	c = Counter(b)
	ckey = c.values()
	cmode = statistics.multimode(ckey)
	print(min(cmode))


for _ in range(int(input())):
	N = int(input())
	lst = list(map(lambda x: int(x), input().split(' ')))
	s = set(lst)
	d = dict()
	for ele in s:
		d[ele] = lst.count(ele)
	d1 = dict()
	for ele in d.values():
		if ele in d1:
			d1[ele] += 1
		else:
			d1[ele] = 1
	lst1 = list(d1.values())
	lst1.sort()
	a = lst1[len(lst1) - 1]
	lst2 = []
	for key in d1.keys():
		if d1[key] == a:
			lst2.append(key)
	print(min(lst2))


t = int(input())
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	d = {}
	for item in l1:
		if item not in d:
			d[item] = 1
		else:
			d[item] = d[item] + 1
	dd = {}
	for v in d.values():
		if v not in dd:
			dd[v] = 1
		else:
			dd[v] = dd[v] + 1
	key = None
	val = 0
	for (k, v) in dd.items():
		if key == None:
			key = k
			val = v
		elif v > val:
			val = v
			key = k
		elif v == val:
			key = min(key, k)
	print(key)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	d = {}
	for j in A:
		if j not in d:
			d[j] = 1
		else:
			d[j] += 1
	fof = {}
	for v in d.values():
		if v not in fof:
			fof[v] = 1
		else:
			fof[v] += 1
	maximumfreq = max(fof.values())
	s = []
	for (k1, v1) in fof.items():
		if fof[k1] == maximumfreq:
			s.append(k1)
	s.sort()
	print(s[0])


def solve():
	n = int(input())
	s = list(map(int, input().split()))
	a = [0] * 10
	k = [0] * 10
	m = 0
	l = 0
	for i in s:
		a[i - 1] += 1
	d = {}
	for i in a:
		if i == 0:
			continue
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	max = 0
	l = 0
	for i in d:
		if d[i] > max:
			max = d[i]
			l = i
		elif i < l and d[i] == max:
			l = i
	print(l)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	a = list(dict.fromkeys(l))
	li = []
	for i in a:
		li.append(l.count(i))
	li.sort()
	maxa = 0
	cot = 0
	e = list(dict.fromkeys(li))
	for i in e:
		if li.count(i) > cot:
			cot = li.count(i)
			maxa = i
	print(maxa)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	a = list(dict.fromkeys(l))
	li = []
	for i in a:
		li.append(l.count(i))
	li.sort()
	g = {}
	e = list(dict.fromkeys(li))
	for i in e:
		g[i] = li.count(i)
	b = max(g.values())
	for (k, v) in g.items():
		if v == b:
			print(k)
			break


t = int(input())
for i in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	l = set(li)
	cou = []
	for s in l:
		cou.append(li.count(s))
	maxi = 0
	sort = sorted(set(cou))
	for j in sort:
		if cou.count(j) > maxi:
			maxi = cou.count(j)
			temp = j
	print(temp)


import os, sys, io, math
from math import *
from array import *
from collections import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	mp = Counter(a)
	cp = {-1: 0}
	for i in mp:
		if mp[i] in cp:
			cp[mp[i]] += 1
		else:
			cp[mp[i]] = 1
	res = 99999999
	c = -999999999
	for i in cp:
		if cp[i] > c:
			c = cp[i]
	for i in cp:
		if cp[i] == c:
			res = min(res, i)
	print(res)


from collections import Counter
T = int(input())
for x in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	b = Counter(arr)
	c = Counter(b.values())
	currentkey = 0
	currentvalue = 0
	for (key, v) in c.items():
		if currentvalue < v:
			currentvalue = v
			currentkey = key
		elif currentvalue == v:
			currentkey = min(currentkey, key)
	print(currentkey)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = dict(Counter([int(x) for x in input().split()]))
	d = dict()
	for (x, y) in a.items():
		d[y] = d.get(y, 0) + 1
	(mx, my) = (-1, -1)
	for (x, y) in d.items():
		if y > my:
			my = y
			mx = x
		elif y == my and x < mx:
			mx = x
	print(mx)


t = int(input())
while t > 0:
	n = int(input())
	list1 = list(map(int, input().split()))
	c = 0
	list2 = []
	list3 = []
	for i in list1:
		if i not in list2:
			list2.append(i)
			c = list1.count(i)
			list3.append(c)
	list4 = []
	list5 = []
	f = 0
	m = 0
	val = 0
	for j in list3:
		if j not in list4:
			list4.append(j)
			c = list3.count(j)
			if f == 0:
				m = c
				val = j
				f = 1
			elif c > m:
				m = c
				val = j
			elif c == m:
				if j < val:
					val = j
					m = c
	print(val)
	t = t - 1


from collections import Counter
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = dict(Counter(a))
	v = list(c.values())
	l = []
	m = max(set(v), key=v.count)
	x = v.count(m)
	for i in set(v):
		if v.count(i) == x:
			l.append(i)
	print(min(l))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	b = Counter(Counter(map(int, input().split())).values())
	max_value = 0
	current_key = 0
	for (key, value) in b.items():
		if max_value < value:
			max_value = value
			current_key = key
		elif max_value == value:
			current_key = min(current_key, key)
	print(current_key)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	d = dict(Counter(l))
	vals = d.values()
	d1 = dict(Counter(vals))
	key = max(d1.values())
	vals = list(d1.values())
	max_vals = []
	if vals.count(key) > 1:
		for i in d1.items():
			if i[1] == key:
				max_vals.append(i[0])
		print(min(max_vals))
	else:
		for i in d1.items():
			if i[1] == key:
				print(i[0])


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	s = set(arr)
	c = []
	for i in s:
		c.append(arr.count(i))
	maxi = 0
	cou = sorted(set(c))
	for j in cou:
		if c.count(j) > maxi:
			maxi = c.count(j)
			temp = j
	print(temp)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	num_dict = {}
	for i in a:
		if i in num_dict:
			num_dict[i] += 1
		else:
			num_dict[i] = 1
	counter2 = {}
	for value in num_dict.values():
		if value not in counter2.keys():
			counter2[value] = 1
		else:
			counter2[value] += 1
	smallAns = -10000
	finalAns = 0
	for (key, value) in counter2.items():
		if value > smallAns:
			smallAns = value
			finalAns = key
		elif value == smallAns:
			if key < finalAns:
				finalAns = key
	print(finalAns)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d1 = {}
	d2 = {}
	for i in l:
		d1[i] = d1.get(i, 0) + 1
	count = sorted(d1.values())
	for i in count:
		d2[i] = d2.get(i, 0) + 1
	maxi = -float('inf')
	for i in d2:
		if d2[i] > maxi:
			mode = i
			maxi = d2[i]
	print(mode)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = dict(Counter(a))
	e = {}
	for (i, c) in d.items():
		if c in e:
			e[c].append(i)
		else:
			e[c] = [i]
	l = [len(v) for v in e.values()]
	if all((i == l[0] for i in l)):
		print(min(e))
	else:
		m = max((len(v) for v in e.values()))
		f = [k for (k, v) in e.items() if len(v) == m]
		print(min(f))


t = int(input())
for _ in range(t):
	n = int(input())
	lst_a = list(map(int, input().split()))
	set_a = set(lst_a)
	new_lst = []
	for i in set_a:
		new_lst.append(lst_a.count(i))
	set_b = sorted(set(new_lst))
	f = 0
	for j in set_b:
		if f < new_lst.count(j):
			f = new_lst.count(j)
			t = j
	print(t)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = set(a)
	a1 = []
	for i in l:
		a1.append(a.count(i))
	l = sorted(set(a1))
	freq = 0
	for i in l:
		if freq < a1.count(i):
			freq = a1.count(i)
			t = i
	print(t)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))[:n]
	mode = dict()
	for i in a:
		mode[i] = mode.get(i, 0) + 1
	freq = dict()
	maxi = -1
	for i in mode:
		freq[mode[i]] = freq.get(mode[i], 0) + 1
		if freq[mode[i]] >= maxi:
			maxi = freq[mode[i]]
	mini = 1000000
	for i in freq:
		if freq[i] == maxi and i < mini:
			mini = i
	print(mini)


t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	l.sort()
	l1 = set(l)
	b = list()
	for nj in l1:
		b.append(l.count(nj))
	b.sort()
	(x, y) = (0, 0)
	for i in b:
		if x < b.count(i):
			x = b.count(i)
			y = i
	print(y)


from statistics import mode
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	i = 0
	b = []
	while i <= n - 1:
		b.append(a.count(a[i]))
		i += a.count(a[i])
	b.sort()
	f = 0
	t = 0
	for i in b:
		if f < b.count(i):
			f = b.count(i)
			t = i
	print(t)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	st = set(arr)
	frequencies = []
	for i in st:
		frequencies.append(arr.count(i))
	st = sorted(set(frequencies))
	f = 0
	for j in st:
		if f < frequencies.count(j):
			f = frequencies.count(j)
			t = j
	print(t)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = {}
	for i in l:
		if i not in s:
			s[i] = 1
		else:
			s[i] = s[i] + 1
	a = []
	for i in s.values():
		a.append(i)
	r = {}
	for k in a:
		if k not in r:
			r[k] = 1
		else:
			r[k] = r[k] + 1
	max_keys = [key for (key, value) in r.items() if value == max(r.values())]
	print(min(max_keys))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	h = {}
	a.sort()
	prev = -1
	for i in a:
		if i != prev:
			h[i] = 0
			prev = i
		h[i] += 1
	l = list(h.values())
	modes = {i: 0 for i in set(l)}
	for mode in l:
		modes[mode] += 1
	vals = list(modes.values())
	maxMode = max(vals)
	if vals.count(maxMode) == 1:
		print(list(modes.keys())[vals.index(maxMode)])
	else:
		print(sorted(filter(lambda i: i[1] == maxMode, modes.items()))[0][0])


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	freq = {}
	for i in arr:
		freq[i] = freq.get(i, 0) + 1
	count = sorted(freq.values())
	ans = {}
	for i in count:
		ans[i] = ans.get(i, 0) + 1
	ans = sorted(ans.items(), reverse=True, key=lambda x: x[1])
	high = ans[0][1]
	ans = [i[0] for i in ans if i[1] == high]
	print(min(ans))


for i in range(int(input())):
	n = int(input())
	assign = list(map(int, input().split()))
	assign.sort()
	setassign = set(assign)
	frequencies = []
	k = 0
	for i in setassign:
		frequencies.append(assign.count(i))
	frequencies.sort()
	setfreq = {}
	for i in frequencies:
		setfreq.update({i: frequencies.count(i)})
	a = list(setfreq.keys())
	b = list(setfreq.values())
	index = b.index(max(b))
	print(a[index])


t = int(input())
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	lis = []
	z = list(set(x))
	for i in range(len(z)):
		lis.append(x.count(z[i]))
	lis.sort()
	myd = {}
	for i in range(len(lis)):
		myd.update({lis[i]: lis.count(lis[i])})
	k = list(myd.keys())
	v = list(myd.values())
	ind = v.index(max(v))
	print(k[ind])


n = int(input())
for i in range(n):
	leng = int(input())
	list1 = [int(a) for a in input().split()]
	(dict1, dict2) = ({}, {})
	for j in list1:
		if j in dict1:
			dict1[j] += 1
		else:
			dict1[j] = 1
	for j in dict1:
		x = dict1[j]
		if x in dict2:
			dict2[x] += 1
		else:
			dict2[x] = 1
	sorted_dict = sorted(dict2.items(), key=lambda x: x[0])
	dict2 = dict(sorted_dict)
	Keymax = max(dict2, key=lambda x: dict2[x])
	print(Keymax)