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

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
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) 

# cook your dish here
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
 else:
  if v[x] == 1:
   count += 1
  
print(count) 

# cook your dish here
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)

# cook your dish here
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): 
 
 # Creating an empty dictionary  
 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)

# cook your dish here
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)

#!/usr/bin/env python
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)

# cook your dish here
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)

# cook your dish here
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 
#print(freq)
day=0
for i in freq.values():
 if i%2==0:
  day=day+(i//2)
 else:
  day=day+(i//2)+1
  
print(day)

# cook your dish here
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)

# cook your dish here
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)

# cook your dish here
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)

# cook your dish here
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()))
#print(set(A))
b=0
c=0
d=0
for j in set(A):
 b=math.ceil(A.count(j)/2)
 d+=b
 #print(b,d,c)
print(d+c)


# cook your dish here
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_)

# cook your dish here
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