Dinesh is very fond of sweets recently his aunt Riya gifted him an array $a$ of sweets of size $N$. The ith sweet is of the type $a[i]$. His mother told him that he can choose one type of sweet in a day and eat at most 2 sweets of that type. Since he has to eat all the sweets as quickly as possible because his cousins are arriving. Find out the minimum number of days in which he can eat all the sweets gifted by his aunt Riya. 

-----Input:-----
- First-line will contain $N$, the number of sweets.  
- The next line will contain $N$ space integers denoting the type of sweets.

-----Output:-----
Output the minimum number of days in which he can eat all the sweets.

-----Constraints-----
- $1 \leq N \leq 10000$
- $1 \leq a[i] \leq 10^3$

-----Sample Input:-----
3
1 2 2

-----Sample Output:-----
2

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
n = int(input())
lst = list(map(int, input().split()))
dict1 = {}.fromkeys(lst, 0)
for key in lst:
	dict1[key] += 1
sum1 = 0
for key in dict1:
	sum1 += dict1[key] // 2
	if dict1[key] % 2 == 1:
		sum1 += 1
print(sum1)


n = int(input())
a = list(map(int, input().split()))
v = dict()
count = 0
for i in range(n):
	k = a[i]
	if k in v:
		v[k] += 1
	else:
		v[k] = 1
for x in v:
	if v[x] >= 2:
		if v[x] % 2 == 0:
			count += v[x] // 2
		else:
			count += v[x] // 2
			count += 1
	elif v[x] == 1:
		count += 1
print(count)


n = int(input())
lst = list(map(int, input().split()))
d = dict()
sm = 0
for i in lst:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
for i in d:
	if d[i] % 2 == 0:
		sm += d[i] // 2
	else:
		sm += (d[i] + 1) // 2
print(sm)


n = int(input())
a = list(map(int, input().split()))
a.sort()
count = 0
i = 0
while len(a) != 0 and len(a) != 1:
	if a[i] == a[i + 1]:
		a.pop(0)
		a.pop(0)
	else:
		a.pop(0)
	count += 1
if len(a) == 1:
	count += 1
print(count)


n = int(input())
lis = list(map(int, input().split()))
dic = {}
for i in lis:
	if i in dic:
		dic[i] += 1
	else:
		dic[i] = 1
cnt = 0
for i in dic:
	while dic[i] >= 2:
		dic[i] -= 2
		cnt += 1
	if dic[i] != 0:
		cnt += 1
print(cnt)


n = int(input())
a = list(map(int, input().split()))
b = set(a)
c = 0
for j in b:
	x = a.count(j)
	c += x // 2 + x % 2
print(c)


n = int(input())
arr = list(map(int, input().split()))
arr.sort()
i = 0
count = 0
while i < n:
	if i == n - 1:
		i += 1
		count += 1
		continue
	if arr[i] == arr[i + 1]:
		i += 2
	else:
		i += 1
	count += 1
print(count)


from collections import Counter
nos_sweet = int(input())
sweet_types = Counter([int(x) for x in input().split()])
days = 0
for (_, v) in list(sweet_types.items()):
	(d, r) = divmod(v, 2)
	days += d + r
print(days)


from collections import Counter
ll = int(input())
n = list(map(int, input().rstrip().split(' ')))
l = Counter(n)
lst = []
for (i, j) in l.items():
	if j % 2 == 0:
		lst.append(j // 2)
	else:
		lst.append(j // 2 + 1)
print(sum(lst))


import math

def CountFrequency(my_list):
	freq = {}
	x = []
	for item in my_list:
		if item in freq:
			freq[item] += 1
		else:
			freq[item] = 1
	for (key, value) in freq.items():
		x.append(math.ceil(value / 2))
	return sum(x)
n = int(input())
a = list(map(int, input().split()))[:n]
print(CountFrequency(a))


n = int(input())
a = [int(i) for i in input().split()]
temp = set(a)
count = 0
for i in temp:
	t = a.count(i)
	if t % 2 == 0:
		count += int(t / 2)
	else:
		count += int(t / 2) + 1
print(count)


from math import ceil
tc = int(input())
sw = list(map(int, input().split()))
sw.sort()
b = list(set(sw))
sol = 0
for i in b:
	sol = sol + ceil(sw.count(i) / 2)
print(sol)


from collections import Counter
sweets_number = int(input())
sweets_types = list(map(int, input().split()))
sweets_types_frequencies = Counter(sweets_types)
days = sum(((count + 1) // 2 for count in list(sweets_types_frequencies.values())))
print(days)


from collections import Counter
noOfSweets = int(input())
typeOfParticularSweet = list(map(int, input().split()))
frequencySweet = Counter(typeOfParticularSweet)
noOfDaysReq = 0
for i in frequencySweet.values():
	if i == 1:
		noOfDaysReq += 1
	elif i % 2 == 0:
		noOfDaysReq += i // 2
	else:
		noOfDaysReq += i // 2 + 1
print(noOfDaysReq)


n = int(input())
arr = list(map(int, input().split()))
dr = {}
for i in arr:
	if i in dr.keys():
		dr[i] += 1
	else:
		dr[i] = 1
ct = 0
for i in dr.keys():
	if dr[i] % 2 == 0:
		ct += dr[i] // 2
	else:
		ct += dr[i] // 2 + 1
print(ct)


n = int(input())
lst = list(map(int, input().split()))
freq = {}
for i in lst:
	if i not in freq:
		freq[i] = 1
	else:
		freq[i] += 1
day = 0
for i in freq.values():
	if i % 2 == 0:
		day = day + i // 2
	else:
		day = day + i // 2 + 1
print(day)


n = int(input())
l = list(map(int, input().split()))
d = {}
days = {}
ans = 0
for i in l:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
for (key, value) in d.items():
	if d[key] % 2 == 0:
		ans += d[key] // 2
	else:
		ans = ans + d[key] // 2 + 1
print(ans)


test = int(input())
x = list(map(int, input().strip().split()))
if test == len(x):
	x.sort()
	day = 1
	count = len(x) - 1
	while count > 0:
		if x[count - 1] == x[count]:
			count -= 1
		day += 1
		count -= 1
	print(day)


n = int(input())
l = list(map(int, input().split()))[:n]
d = {}
for i in l:
	d[i] = d.get(i, 0) + 1
s = 0
for (key, value) in d.items():
	s += value // 2 + value % 2
print(s)


n = int(input())
arr = list(map(int, input().split()))
se = set(arr)
c = []
total = 0
for x in se:
	c.append(arr.count(x))
for x in c:
	total += x // 2
	total += x % 2
print(total)


import math
N = list(map(int, input().strip().split()))
A = list(map(int, input().strip().split()))
b = 0
c = 0
d = 0
for j in set(A):
	b = math.ceil(A.count(j) / 2)
	d += b
print(d + c)


n = int(input())
lis = list(map(int, input().split()))[:n]
arr = list(set(lis))
sum_ = 0
for i in range(len(arr)):
	sum_ += lis.count(arr[i]) // 2 + lis.count(arr[i]) % 2
print(sum_)


from itertools import groupby
try:
	N = int(input())
	sweet = list(map(int, input().split()))
	sweet = sorted(sweet)
	l = [len(list(group)) for (key, group) in groupby(sweet)]
	for i in range(len(l)):
		if l[i] % 2 == 0:
			pass
		else:
			l[i] += 1
	print(sum(l) // 2)
except:
	pass