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

There are N students in a class, where the i-th student has a score of A_{i}.

The i-th student will *boast* if and only if the number of students scoring less than or equal A_{i} is greater than the number of students scoring greater than A_{i}.

Find the number of students who will boast.

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

- The first line contains T - the number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer N - the number of students.
- The second line of each test case contains N integers A_{1}, A_{2}, \dots, A_{N} - the scores of the students.

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

For each test case, output in a single line the number of students who will boast.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 100$
$0 ≤ A_{i} ≤ 100$

----- Sample Input 1 ------ 
3
3
100 100 100
3
2 1 3
4
30 1 30 30

----- Sample Output 1 ------ 
3
2
3

----- explanation 1 ------ 
- Test case $1$: All three students got the highest score. So all three of them will boast.
- Test case $2$: Only the student with score $1$ will not be able to boast. 
- Test case $3$: Only the student with score $1$ will not be able to boast.

Source: codechef | Difficulty: MEDIUM
Tags: Sorting

Data structures

Range queries

Complete search


Solutions:
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = Counter([int(x) for x in input().strip().split()])
	a = [(x, y) for (x, y) in a.items()]
	a.sort(key=lambda x: x[0], reverse=True)
	(ans, i) = (0, 0)
	while ans < n / 2 and i < len(a):
		ans += a[i][1]
		i += 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	count = 0
	if a[n // 2] == a[n // 2 - 1]:
		count = a[:n // 2].count(a[n // 2])
	if n % 2 != 0:
		count += 1
	print(n // 2 + count)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())))
	i = n // 2
	while i > 0 and l[i] == l[i - 1]:
		i -= 1
	print(n - i)


def find_boasting_students(n, scores):
	count = 0
	for i in range(n):
		num_greater = 0
		num_less_equal = 0
		for j in range(n):
			if scores[j] > scores[i]:
				num_greater += 1
			elif scores[j] <= scores[i]:
				num_less_equal += 1
		if num_less_equal > num_greater:
			count += 1
	return count
t = int(input())
for _ in range(t):
	n = int(input())
	scores = list(map(int, input().split()))
	count = find_boasting_students(n, scores)
	print(count)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		cless = 0
		cmore = 0
		for j in range(n):
			if l[i] >= l[j]:
				cless += 1
			else:
				cmore += 1
		if cmore < cless:
			ans += 1
	print(ans)


import statistics
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	med = statistics.median(arr)
	count = 0
	for i in arr:
		if i >= med:
			count += 1
	print(count)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	boast = 0
	for i in range(len(A)):
		(a, b) = (0, 0)
		for j in range(len(A)):
			if A[i] >= A[j]:
				a = a + 1
			else:
				b = b + 1
		if a > b:
			boast = boast + 1
	print(boast)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	temp = a[int(n / 2):]
	set_a = set(temp)
	ans = 0
	for each in set_a:
		ans += a.count(each)
	print(ans)


def max_num(i, kk2):
	kk2 = kk2[::-1]
	p = 0
	for k in range(len(kk2)):
		if kk2[k] == i:
			p = len(kk2) - k
			break
	kk2 = kk2[::-1]
	return p
i = int(input())
listk = []
for _ in range(i):
	p = int(input())
	kk = input().split()
	kk2 = []
	for ele in kk:
		kk2.append(int(ele))
	kk2.sort()
	sta = 0
	for ele in kk2:
		if max_num(ele, kk2) > len(kk2) - max_num(ele, kk2):
			sta = sta + 1
	listk.append(sta)
for ele in listk:
	print(ele)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for j in l:
		s = 0
		k = 0
		for z in l:
			if z <= j:
				s += 1
			elif z > j:
				k += 1
		if s > k:
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	count = 0
	for i in range(n):
		less = i
		large = n - 1 - i
		same = a[i + 1:n].count(a[i])
		if i + same >= large - same:
			count += 1
	print(count)


t = int(input())
lc = []
for _ in range(0, t):
	N = int(input())
	score_students = list(map(int, input().split(' ')))
	lc.append(score_students)
for i in lc:
	ofr = 0
	for j in i:
		l = 0
		m = 0
		for k in i:
			if k <= j:
				l += 1
			else:
				m += 1
		if l > m:
			ofr += 1
	print(ofr)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	count = 0
	if n % 2 != 0:
		mid = arr[n // 2]
		count += n // 2 + 1
		c1 = arr[0:n // 2].count(mid)
		count += c1
	else:
		mid = arr[n // 2]
		mid_1 = arr[n // 2 - 1]
		if mid == mid_1:
			count += n // 2
			c1 = arr[0:n // 2].count(mid)
			count += c1
		else:
			count += n // 2
	print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	i = 0
	while i < n:
		if i != n - 1 and arr[i] == arr[i + 1]:
			i += 1
			continue
		if i >= n - i - 1:
			break
		i += 1
	print(arr.count(arr[i]) + n - i - 1)


from collections import Counter

class Solver:

	def solve(self, array, length):
		counter = Counter(array)
		keys = sorted(counter)
		prevt = 0
		nextt = sum(counter.values())
		ans = 0
		for key in keys:
			prevt += counter[key]
			nextt -= counter[key]
			if prevt > nextt:
				ans += counter[key]
		return ans

class Driver:

	def __init__(self):
		self._solver = Solver()

	def drive(self):
		test_cases = int(input().strip())
		for _ in range(test_cases):
			length = int(input().strip())
			array = list(map(int, input().strip().split(' ')))
			ans = self._solver.solve(array, length)
			print(ans)
Driver().drive()


for _ in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split(' ')))
	list1.sort()
	m = int(n / 2)
	list2 = []
	for i in list1[m:]:
		if i not in list2:
			list2.append(i)
	count = 0
	for i in list2:
		if i in list1:
			count += list1.count(i)
	print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = 0
	for i in range(n):
		(s, b) = (0, 0)
		for j in range(n):
			if arr[j] <= arr[i]:
				s += 1
			elif arr[j] > arr[i]:
				b += 1
		if s > b:
			cnt += 1
	print(cnt)


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	count = 0
	for i in range(n):
		l = 0
		m = 0
		for j in range(n):
			if lst[j] <= lst[i]:
				l += 1
			elif lst[j] > lst[i]:
				m += 1
		if l > m:
			count += 1
	print(count)


n = int(input())
for i in range(n):
	k = int(input())
	l = list(map(int, input().split()))
	cnt = 0
	for i in range(k):
		a = 0
		b = 0
		for j in range(k):
			if l[i] >= l[j]:
				a += 1
			else:
				b += 1
		if a > b:
			cnt += 1
	print(cnt)


t = int(input())
for i in range(t):
	n = int(input())
	score = sorted(list(map(int, input().split())))
	count = 0
	for i in range(n):
		lessNum = i
		sameNum = score[i + 1:n].count(score[i])
		largeNum = n - 1 - i
		if lessNum + sameNum >= largeNum - sameNum:
			count += 1
	print(count)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	total = 0
	for i in range(N):
		mini = 0
		maxi = 0
		for j in A:
			if j <= A[i]:
				mini += 1
			else:
				maxi += 1
		if mini > maxi:
			total += 1
	print(total)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		c1 = 0
		c2 = 0
		for j in range(n):
			if l[i] >= l[j]:
				c2 += 1
			else:
				c1 += 1
		if c2 > c1:
			ans += 1
	print(ans)


T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	for i in range(len(arr)):
		arr[i] = int(arr[i])
	arr = sorted(arr)
	print(N - arr.index(arr[N // 2]))


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	(lt, g, c) = (0, 0, 0)
	for i in range(n):
		(lt, g) = (0, 0)
		for j in range(n):
			if i == j:
				continue
			if s[j] <= s[i]:
				lt += 1
			else:
				g += 1
		if lt >= g:
			c += 1
	print(c)


def average_flex(list, n):
	boast = 0
	for i in range(0, n):
		(flex, nflex) = (0, 0)
		for j in range(0, n):
			if list[i] >= list[j]:
				flex = flex + 1
			else:
				nflex = nflex + 1
		if flex > nflex:
			boast = boast + 1
	return boast
list1 = []
nlist = []
T = int(input())
for i in range(0, T):
	nlist.append(int(input()))
	list1.append(list(map(int, input().split())))
for i in range(0, T):
	print(average_flex(list1[i], nlist[i]))


for _ in range(int(input())):
	(n, m) = (int(input()), sorted(list(map(int, input().split(' ')))))
	b = 0
	for i in range(n):
		lits = gits = 0
		for j in range(n):
			if m[j] <= m[i]:
				lits += 1
			else:
				gits += 1
		if lits > gits:
			b += 1
	print(b)


for _ in range(int(input())):
	(n, m) = (int(input()), sorted(list(map(int, input().split(' ')))))
	b = 0
	for i in range(n):
		lts = gts = 0
		for j in range(n):
			if m[j] <= m[i]:
				lts += 1
			else:
				gts += 1
		if lts > gts:
			b += 1
	print(b)


for _ in range(int(input())):
	N = int(input())
	lst = list(map(int, input().split(' ')))
	f = 0
	for i in range(len(lst)):
		g = 0
		l = 0
		for j in range(len(lst)):
			if lst[j] > lst[i]:
				g += 1
			else:
				l += 1
		if l > g:
			f += 1
	print(f)


a = int(input())
for i in range(a):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	lo = 0
	hi = n
	mid = (lo + hi) // 2
	c = 0
	if l[mid] == l[mid - 1]:
		c += l[:mid].count(l[mid])
	if n % 2 != 0:
		c += 1
	print(mid + c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	for i in range(0, len(a)):
		lc = 0
		gc = 0
		for j in range(0, len(a)):
			if i != j:
				if a[j] <= a[i]:
					lc += 1
				else:
					gc += 1
		if lc >= gc:
			cnt += 1
	print(cnt)


def isBoast(students, index):
	score = students[index]
	cntLess = 0
	cntMore = 0
	for i in range(0, len(students)):
		if score >= students[i]:
			cntLess = cntLess + 1
		else:
			cntMore = cntMore + 1
	return cntLess > cntMore

def main(students):
	cnt = 0
	for i in range(0, len(students)):
		if isBoast(students, i):
			cnt = cnt + 1
	return cnt
try:
	n = int(input())
	for i in range(0, n):
		N = int(input())
		students = list(map(int, input().split()))
		print(main(students))
except EOFError as e:
	print()


for x in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	c = 0
	if l[n // 2] == l[n // 2 - 1]:
		c = l[:n // 2].count(l[n // 2])
	if n % 2 != 0:
		c += 1
	print(n // 2 + c)


t = int(input())
for _ in range(t):
	N = int(input())
	A = [int(x) for x in input().split()]
	A = sorted(A)
	A_d = {}
	for mark in A:
		if mark in A_d:
			A_d[mark] += 1
		else:
			A_d[mark] = 1
	count = 0
	sum = 0
	for key in A_d:
		sum += A_d[key]
		if N - sum < sum:
			count += A_d[key]
	print(count)


for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	ar.sort()
	k = n // 2 - 1
	d = k + 1
	ans = n // 2 if n % 2 == 0 else n // 2 + 1
	for i in range(k, -1, -1):
		if ar[i] == ar[d]:
			ans += 1
		else:
			break
	print(ans)


for _ in range(int(input())):
	nun = int(input())
	wr = list(map(int, input().split()))
	wr.sort()
	medium = wr[len(wr) // 2]
	children = 0
	boast = 0
	for i in range(len(wr)):
		if wr[i] >= medium:
			boast += 1
	print(boast)


for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	w.sort()
	mid = w[len(w) // 2]
	student = 0
	boast = 0
	for i in range(len(w)):
		if w[i] >= mid:
			boast += 1
	print(boast)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n):
		(l, g) = (0, 0)
		for j in range(n):
			if a[j] <= a[i]:
				l += 1
			else:
				g += 1
		if l > g:
			c += 1
	print(c)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	(m, M, c) = (0, 0, 0)
	for i in range(a):
		(m, M) = (0, 0)
		for j in range(a):
			if b[j] <= b[i]:
				m += 1
			if b[j] > b[i]:
				M += 1
		if m > M:
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in range(n):
		(s, g) = (0, 0)
		for j in range(n):
			if l[j] <= l[i]:
				s += 1
			elif l[j] > l[i]:
				g += 1
		if s > g:
			c += 1
	print(c)


t = int(input())
while t > 0:
	n = int(input())
	list1 = list(map(int, input().split()))
	C = 0
	for i in range(0, len(list1)):
		c1 = 0
		c3 = 0
		for j in range(0, len(list1)):
			if i != j:
				if list1[j] <= list1[i]:
					c1 = c1 + 1
				elif list1[j] > list1[i]:
					c3 = c3 + 1
		if c1 >= c3:
			C = C + 1
	print(C)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = []
	for i in range(n):
		l1 = []
		h = []
		c = l[i]
		for j in range(n):
			if i != j:
				if l[j] > c:
					h.append(l[j])
				elif l[j] <= c:
					l1.append(l[j])
		l1.append(c)
		if len(l1) > len(h):
			t.append(l[i])
	print(len(t))


t = int(input())
lc = []
for mml in range(0, t):
	l = int(input())
	jk = str(input())
	tp = []
	for kkc in jk.split(' '):
		tp.append(int(kkc))
	lc.append(tp)
for bb in lc:
	ofr = 0
	for iir in range(0, len(bb)):
		l = 0
		m = 0
		for kke in range(0, len(bb)):
			if bb[kke] <= bb[iir]:
				l += 1
			else:
				m += 1
		if l > m:
			ofr += 1
	print(ofr)


T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	m = N // 2
	M = A[m]
	for i in range(m - 1, -1, -1):
		if A[i] == M:
			m = i
		else:
			break
	print(N - m)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	(b, c, d) = (0, 0, 0)
	while c < n:
		(x, y) = (0, 0)
		d = 0
		while d < n:
			if a[d] <= a[c]:
				x += 1
			else:
				y += 1
			d += 1
		if x > y:
			b += 1
		c += 1
	t -= 1
	print(b)


for i in range(int(input())):
	n = int(input())
	lis = list(map(int, input().strip().split(' ')))
	lis.sort()
	r = (n + 1) // 2
	s = r
	if n % 2 != 0:
		s = r - 1
	for j in range(1, n // 2 + 1):
		if lis[s - j] == lis[s]:
			r += 1
		else:
			break
	print(r)


for _ in range(int(input())):
	i = int(input())
	j = list(map(int, input().split()))
	j.sort()
	if i % 2 == 0:
		mid = (j[i // 2 - 1] + j[i // 2]) / 2
	else:
		mid = j[i // 2]
	ans = 0
	for val in j:
		if val >= mid:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	x = []
	c = 0
	for i in range(n // 2, n):
		if a[i] not in x:
			c += a.count(a[i])
			x.append(a[i])
	print(c)


for _ in range(int(input())):
	N = int(input())
	A = sorted(list(map(int, input().split())))
	z = 0
	ans = 0
	i = 0
	while i < N:
		j = 1
		z += 1
		while i != N - 1 and A[i] == A[i + 1]:
			z += 1
			j += 1
			i += 1
		if z > N - z:
			ans += j
		i += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	count = 0
	for i in range(n):
		j = 0
		c1 = 0
		c2 = 0
		while j < n:
			if j == i:
				j += 1
				continue
			if a[j] <= a[i]:
				c1 += 1
			else:
				c2 += 1
			j += 1
		if c1 >= c2:
			count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	l = n // 2
	c = 0
	if a[l] == a[l - 1]:
		c = a[0:l].count(a[l])
	ans = n // 2 + c
	if n % 2 == 0:
		print(ans)
	else:
		print(ans + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	if n % 2 == 0:
		d = int(n / 2)
	else:
		d = int((n - 1) / 2)
	e = l[d]
	j = l.index(e)
	print(n - j)


n = int(input())
for i in range(n):
	n1 = int(input())
	l = list(map(int, input().split()))
	l.sort()
	c = 0
	a = l[n1 // 2]
	for i in l:
		if i >= a:
			c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	c = 0
	for j in range(n):
		max = j
		min = j
		while min < n - 1:
			if l[min] != l[min + 1]:
				break
			else:
				max += 1
			min += 1
		max += 1
		if max > n - max:
			c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	k.sort()
	c = 0
	for j in range(n):
		cc = j
		j1 = j
		while j1 < n - 1:
			if k[j1] != k[j1 + 1]:
				break
			else:
				cc += 1
			j1 += 1
		cc += 1
		if cc > n - cc:
			c += 1
	print(c)


for _ in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	lst = []
	for i in a:
		high = 0
		low = 0
		for j in a:
			if i >= j:
				low += 1
			else:
				high += 1
		if low > high:
			lst.append(i)
	print(len(lst))