Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Arrays have fallen out of Chef's good books, and he plans to destroy all arrays he possesses. He is left with the last array A, consisting of N positive integers.  In order to destroy the array, he can perform the following 2 types of operations any number of times.

Choose any 2 elements, say X and Y, from the given array A such that X != Y, and remove them, or
Choose any 1 element, say X, from A, and remove it.

In order to destroy the array as quickly as possible, Chef is interested in knowing the minimum number of operations required to destroy it. Please help him achieve this task.

------ Input ------ 

The first line of input contains a single integer T denoting the number of test cases. First line of each test case contains a single integer N — the number of integers in the array A.

Second line of each test case contains N space separated integers denoting the array A.

------ Output ------ 

For each test case, output the required answer in a new line.

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

1 ≤ T ≤ 50000
1 ≤ N ≤ 50000
1 ≤ A_{i} ≤ 10^{9}
sum of N over all test cases does not exceed 5 × 10^{5}

----- Sample Input 1 ------ 
3

2

1 2

2

1 1

3

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

2

2
----- explanation 1 ------ 

Test 1: In an operation, Chef can choose 2 elements X and Y such that X = 1 and Y = 2 and can destroy them as X != Y.
Test 2: Chef cannot choose 2 elements X and Y such that X != Y. So, he has to use the second operation twice in order to destroy the array.

Difficulty: HARD
Tags: Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	count = 1
	flag = 0
	for i in range(len(arr) - 1):
		if arr[i] == arr[i + 1]:
			count += 1
		else:
			flag = max(flag, count)
			count = 1
	flag = max(flag, count)
	print(max(flag, int((n + 1) // 2)))


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


import heapq
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	c = Counter(a)
	p = [-j for (i, j) in c.items()]
	heapq.heapify(p)
	count = 0
	while p[0] < 0:
		a = heapq.heappop(p)
		if len(p) > 0:
			b = heapq.heappop(p)
			heapq.heappush(p, a + 1)
			heapq.heappush(p, b + 1)
		else:
			heapq.heappush(p, a + 1)
		count += 1
	print(count)


class MaxHeap:

	def __init__(self, collection=None):
		self._heap = []
		if collection is not None:
			for el in collection:
				self.push(el)

	def push(self, value):
		self._heap.append(value)
		_sift_up(self._heap, len(self) - 1)

	def pop(self):
		_swap(self._heap, len(self) - 1, 0)
		el = self._heap.pop()
		_sift_down(self._heap, 0)
		return el

	def __len__(self):
		return len(self._heap)

	def print(self, idx=1, indent=0):
		print('\t' * indent, f'{self._heap[idx - 1]}')
		(left, right) = (2 * idx, 2 * idx + 1)
		if left <= len(self):
			self.print(left, indent=indent + 1)
		if right <= len(self):
			self.print(right, indent=indent + 1)

def _swap(L, i, j):
	(L[i], L[j]) = (L[j], L[i])

def _sift_up(heap, idx):
	parent_idx = (idx - 1) // 2
	if parent_idx < 0:
		return
	if heap[idx] > heap[parent_idx]:
		_swap(heap, idx, parent_idx)
		_sift_up(heap, parent_idx)

def _sift_down(heap, idx):
	child_idx = 2 * idx + 1
	if child_idx >= len(heap):
		return
	if child_idx + 1 < len(heap) and heap[child_idx] < heap[child_idx + 1]:
		child_idx += 1
	if heap[child_idx] > heap[idx]:
		_swap(heap, child_idx, idx)
		_sift_down(heap, child_idx)

def heap_sort(collection):
	heap = MaxHeap(collection)
	sorted_arr = []
	while len(heap) > 0:
		sorted_arr.append(heap.pop())
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		try:
			d[i] += 1
		except:
			d[i] = 1
	x = MaxHeap()
	for i in d.values():
		x.push(i)
	ans = 0
	while len(x) > 1:
		a = x.pop()
		b = x.pop()
		ans += 1
		a -= 1
		b -= 1
		if a > 0:
			x.push(a)
		if b > 0:
			x.push(b)
	while len(x) > 0:
		ans += x.pop()
	print(ans)


import heapq
for _ in range(int(input())):
	n = int(input())
	heap = list(map(int, input().split()))
	dic = {}
	ans = 0
	for i in heap:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	temp = []
	for i in dic:
		heapq.heappush(temp, [-dic[i], i])
	while temp:
		if len(temp) > 1:
			mx = heapq.heappop(temp)
			mx2 = heapq.heappop(temp)
			if mx[0] != -1:
				if mx2[0] != -1:
					heapq.heappush(temp, [mx2[0] + 1, mx2[1]])
				heapq.heappush(temp, [mx[0] + 1, mx[1]])
				ans += 1
			else:
				ans += 1
		else:
			mn = heapq.heappop(temp)
			if mn[0] != -1:
				heapq.heappush(temp, [mn[0] + 1, mn[1]])
				ans += 1
			else:
				ans += 1
	print(ans)


import heapq as heap
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	c = Counter()
	for v in h:
		c[v] += 1
	h = []
	for v in c:
		h.append(-1 * c[v])
	heap.heapify(h)
	ans = 0
	while h:
		try:
			last = h[1]
		except:
			ans += -1 * h[0]
			break
		e1 = -1 * heap.heappop(h)
		e2 = -1 * heap.heappop(h)
		ans += 1
		e1 -= 1
		e2 -= 1
		if e1:
			heap.heappush(h, -1 * e1)
		if e2:
			heap.heappush(h, -1 * e2)
	print(ans)


from math import ceil
test = int(input())
while test:
	test -= 1
	n = int(input())
	a = [int(i) for i in input().split()]
	dic = {}
	for i in a:
		dic[i] = 0
	for i in a:
		dic[i] += 1
	ans = 0
	maxi = max(dic.values())
	if len(a) - maxi >= maxi:
		print(ceil(len(a) / 2))
	else:
		ans = len(a) - maxi
		maxi = maxi - ans
		ans += maxi
		print(ans)


import heapq
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = {}
	for i in a:
		d[i] = d.setdefault(i, 0) - 1
	hp = []
	for i in d:
		heapq.heappush(hp, (d[i], i))
	ans = 0
	while len(hp) > 1:
		x = heapq.heappop(hp)
		y = heapq.heappop(hp)
		ans += 1
		if x[0] + 1 < 0:
			heapq.heappush(hp, (x[0] + 1, x[1]))
		if y[0] + 1 < 0:
			heapq.heappush(hp, (y[0] + 1, y[1]))
	if len(hp) == 1:
		x = heapq.heappop(hp)
		ans += -x[0]
	print(ans)


from collections import Counter
for t in range(int(input())):
	n = int(input())
	a = Counter(map(int, input().split()))
	m = max((n + 1) // 2, a.most_common(1)[0][1])
	print(m)


from heapq import *
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
	h = []
	for i in freq:
		heappush(h, -freq[i])
	ans = 0
	while h:
		v2 = None
		v1 = -heappop(h)
		if h:
			v2 = -heappop(h)
		if v2 is None:
			ans += v1
		else:
			ans += 1
			v1 -= 1
			v2 -= 1
			if v1 > 0:
				heappush(h, -v1)
			if v2 > 0:
				heappush(h, -v2)
	print(ans)


from math import ceil
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	hash = {}
	for i in l:
		try:
			hash[i]
		except:
			hash[i] = 1
		else:
			hash[i] += 1
	ans = []
	for i in hash.keys():
		ans.append(hash[i])
	ans.sort(reverse=True)
	print(max((ans[0], ceil(n / 2))))


import heapq
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	d = dict()
	heap = []
	for i in range(n):
		try:
			d[a[i]] -= 1
		except:
			d[a[i]] = -1
	ans = 0
	for pair in d:
		heapq.heappush(heap, [d[pair], pair])
	while heap:
		x = heapq.heappop(heap)
		if heap:
			y = heapq.heappop(heap)
			x[0] += 1
			y[0] += 1
			ans += 1
			if x[0] != 0:
				heapq.heappush(heap, x)
			if y[0] != 0:
				heapq.heappush(heap, y)
		else:
			x[0] *= -1
			ans += x[0]
			break
	print(ans)