AtCoder Beginner Contest 053 - Card Eater

Snuke has decided to play a game using cards.
He has a deck consisting of N cards. On the i-th card from the top, an integer A_i is written.
He will perform the operation described below zero or more times, so that the values written on the remaining cards will be pairwise distinct. Find the maximum possible number of remaining cards. Here, N is odd, which guarantees that at least one card can be kept.
Operation: Take out three arbitrary cards from the deck. Among those three cards, eat two: one with the largest value, and another with the smallest value. Then, return the remaining one card to the deck.

-----Constraints-----
 - 3 ≦ N ≦ 10^{5}
 - N is odd.
 - 1 ≦ A_i ≦ 10^{5}
 - A_i is an integer.

-----Input-----
The input is given from Standard Input in the following format:
N
A_1 A_2 A_3 ... A_{N}

-----Output-----
Print the answer.

-----Sample Input-----
5
1 2 1 3 7

-----Sample Output-----
3

One optimal solution is to perform the operation once, taking out two cards with 1 and one card with 2. One card with 1 and another with 2 will be eaten, and the remaining card with 1 will be returned to deck. Then, the values written on the remaining cards in the deck will be pairwise distinct: 1, 3 and 7.

Source: atcoder | Difficulty: MEDIUM


Solutions:
N = int(input())
a = [int(i) for i in input().split()]
ans = set(a)
if (len(a) - len(ans)) % 2 is 0:
	print(len(ans))
else:
	print(len(ans) - 1)


N = int(input())
A = list(map(int, input().split()))
from collections import Counter
A = Counter(A)
tot = len(A)
cnt = 0
for i in A.most_common():
	if i[1] % 2 == 0:
		cnt += 1
print(tot - cnt % 2)


_ = input()
a = set(map(int, input().split()))
if len(a) % 2 == 0:
	print(len(a) - 1)
else:
	print(len(a))


n = int(input())
from collections import Counter as co
l = co(list(map(int, input().split()))).values()
ans = 0
p = 0
for i in l:
	if (i - 1) % 2 == 0:
		ans += 1
	else:
		p += 1
print(ans + p // 2 * 2)


N = int(input())
A_arr = [int(x) for x in input().split()]
A_set = set(A_arr)
ans = len(A_set)
if ans % 2 == 0:
	ans -= 1
print(ans)


N = int(input())
ARR = list(map(int, input().split()))

def calculate(n, arr):
	dict = {}
	for i in range(n):
		if dict.get(arr[i]) == None:
			dict.__setitem__(arr[i], 1)
		else:
			tmp = dict.get(arr[i])
			dict.__setitem__(arr[i], tmp + 1)
	k1 = len(list(dict.keys()))
	if k1 % 2 == 0:
		print(k1 - 1)
	else:
		print(k1)
calculate(N, ARR)


N = int(input())
A = map(int, input().split())
d = {}
for a in A:
	d[a] = 1
print(len(d) - (0 if len(d) % 2 else 1))


from collections import Counter
ipt = int(input())
nums = Counter(input().split(' ')).most_common()
double = [x[1] for x in nums if x[1] % 2 == 0]
print(len(nums) - len(double) % 2)


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


n = int(input())
a = [int(j) for j in input().split()]
ans = len(set(a))
if (n - ans) % 2 == 0:
	print(ans)
else:
	print(ans - 1)


url = 'https://atcoder.jp//contests/abc057/tasks/abc057_d'
import collections

def main():
	n = int(input())
	cards = list(map(int, input().split()))
	c_cards = collections.Counter(cards)
	credit = 0
	r = 0
	for k in c_cards:
		surplus = c_cards[k] - 1
		r += surplus
		if c_cards[k] > 1:
			n -= surplus
			if credit > 0:
				credit = abs(credit - surplus % 2)
			else:
				credit += surplus % 2
			c_cards[k] -= surplus
	if credit > 0:
		n -= credit
	print(n)

def __starting_point():
	main()
__starting_point()


N = int(input())
A = list(map(int, input().rstrip().split(' ')))
A.sort()
ans = N
for i in range(N - 1):
	if A[i] == A[i + 1]:
		ans -= 1
if ans % 2 == 0:
	ans -= 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
k = len(set(A))
print(k - (k + 1) % 2)


N = int(input())
A = set()
cnt = 0

def count(n, Set):
	if not n in Set:
		Set.add(n)
		return 0
	else:
		return 1
for x in input().split():
	cnt += count(x, A)
if not cnt & 1:
	ans = N - cnt
else:
	ans = N - cnt - 1
print(ans)


n = int(input())
a = map(int, input().split())
kind = len(set(a))
if kind % 2 == 0:
	print(kind - 1)
else:
	print(kind)


n = int(input())
a = list(map(int, input().split()))
d = {}
m = 0
for i in a:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
		m += 1
print(m - 1) if (n - m) % 2 else print(m)


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
from collections import Counter
L = len(Counter(A))
if L % 2 == 0:
	print(L - 1)
else:
	print(L)


import collections
n = int(input())
a = list(map(int, input().split()))
kind = collections.Counter(a)
if len(kind) % 2 == 0:
	print(len(kind) - 1)
else:
	print(len(kind))


N = int(input())
A = list(map(int, input().split()))
cnt = [0 for _ in range(100001)]
for i in range(N):
	cnt[A[i]] = 1
x = cnt.count(1)
y = N - x
if y % 2 == 0:
	print(N - y)
else:
	print(N - y - 1)


n = int(input())
a = (int(i) for i in input().split())
a2 = set(a)
if len(a2) % 2 == 1:
	print(len(a2))
else:
	print(len(a2) - 1)


N = int(input())
A = list(map(int, input().split()))
M = len(set(A))
print(M if M % 2 else M - 1)


from collections import Counter
_ = input()
c = Counter(input().split())
ttl = 0
cnt = 0
for value in c.values():
	ttl += (value + 1) % 2
	cnt += 1
print(cnt - ttl % 2)


n = int(input())
Alist = list(map(int, input().split()))
Blist = set(Alist)
if (len(Alist) - len(Blist)) % 2 == 0:
	print(len(Blist))
else:
	print(len(Blist) - 1)


n = int(input())
a = list(map(int, input().split()))
s = set(a)
k = len(s)
if k % 2 == 0:
	print(k - 1)
else:
	print(k)


_ = input()
A = set(map(int, input().strip().split(' ')))
print(len(A) - (len(A) % 2 == 0))


N = int(input())
A = list(map(int, input().split()))
tmp = [0 for _ in range(10 ** 5)]
for i in range(N):
	tmp[A[i] - 1] += 1
ans = N
flag = False
for i in range(10 ** 5):
	if tmp[i] == 0:
		continue
	elif tmp[i] % 2 == 1:
		ans -= tmp[i] - 1
	elif flag:
		ans -= tmp[i] - 2
		flag = False
	else:
		ans -= tmp[i]
		flag = True
print(ans)


import sys
from collections import Counter
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, *A) = list(map(int, read().split()))
	counter = Counter(A)
	odd = even = 0
	for v in list(counter.values()):
		if v % 2 == 0:
			even += 1
		else:
			odd += 1
	if even % 2 == 0:
		ans = odd + even
	else:
		ans = odd + even - 1
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


from collections import Counter

def main():
	N = int(input())
	A = list(map(int, input().split(' ')))
	counter = Counter(A)
	(n_odd, n_even) = (0, 0)
	for c in counter.values():
		if c % 2 == 0:
			n_even += 1
		else:
			n_odd += 1
	print(n_odd + n_even // 2 * 2)

def __starting_point():
	main()
__starting_point()


N = int(input())
A = [int(i) for i in input().split()]
l = len(set(A))
print(l - (N - l) % 2)


n = int(input())
a = set(list(map(int, input().split())))
print(len(a) + len(a) % 2 - 1)


N = int(input())
(*A,) = map(int, input().split())
c = {}
for a in A:
	c[a] = c.get(a, 0) + 1
print(len(c) - sum((v - 1 for v in c.values())) % 2)


def main():
	from collections import Counter
	(n, *a) = list(map(int, open(0).read().split()))
	s = len(set(a))
	if s % 2 == 1:
		print(s)
	else:
		print(s - 1)

def __starting_point():
	main()
__starting_point()


n = int(input())
a = list(map(int, input().split()))
num_map = dict()
for i in range(n):
	if a[i] not in num_map:
		num_map[a[i]] = 1
	else:
		num_map[a[i]] += 1
counter = 0
for (key, value) in list(num_map.items()):
	if value % 2 == 0:
		num_map[key] = 2
		counter += 1
	else:
		num_map[key] = 1
res = len(num_map) - counter % 2
print(res)


N = int(input())
S = len(set(map(int, input().split())))
print(S - (N - S) % 2)


N = int(input())
a = list(map(int, input().split(' ')))
uni = len(list(set(a)))
if uni % 2 == 0:
	uni -= 1
print(uni)


n = input()
a = set(input().split())
print(len(a) - (len(a) % 2 == 0))


import functools
N = int(input())
A = map(int, input().split())
d = [0 for i in range(10 ** 5 + 1)]
for a in A:
	d[a] = 1
s = sum(d)
print(s - (0 if s % 2 else 1))


n = int(input())
l = len(set(list(map(int, input().split()))))
print(l - 1 if (n - l) % 2 else l)


import sys
readline = sys.stdin.readline
from collections import Counter

def main():
	N = int(readline())
	A = list(map(int, readline().rstrip().split()))
	c = Counter(A)
	for (key, val) in c.items():
		if val > 2:
			if val % 2 == 0:
				c[key] = 2
			else:
				c[key] = 1
	if len([val for (key, val) in c.items() if c[key] == 2]) % 2 == 0:
		print(len(c))
	else:
		print(len(c) - 1)

def __starting_point():
	main()
__starting_point()


n = int(input())
a = list(map(int, input().split()))
d = dict()
for i in a:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
p = 0
k = 0
for i in list(d.values()):
	p += i // 2
	k -= i % 2 - 1
print(n - (p - k // 2) * 2)


N = int(input())
dic = {}
for x in map(int, input().split()):
	dic[x] = dic.setdefault(x, -1) + 1
cnt = 0
for x in dic.values():
	if x % 2 == 1:
		cnt += 1
print(len(dic) - cnt % 2)


N = int(input())
A = list(map(int, input().split()))
B = list(set(A))
if len(B) % 2 == 0:
	print(len(B) - 1)
else:
	print(len(B))


n = int(input())
d = [0] * (10 ** 5 + 1)
a = list(map(int, input().split()))
varies = len(set(a))
for v in a:
	d[v] += 1
two = 0
for i in range(len(d)):
	if d[i] > 0 and d[i] % 2 == 0:
		two += 1
print(varies if two % 2 == 0 else varies - 1)


N = int(input())
k = len(set(list(map(int, input().split()))))
print(k if k % 2 else k - 1)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, *A) = list(map(int, read().split()))
	K = len(set(A))
	if K % 2 == 1:
		ans = K
	else:
		ans = K - 1
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
a = Counter(A)
l_a = len(a)
if l_a % 2 == 0:
	print(l_a - 1)
else:
	print(l_a)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
cnt = Counter(A).most_common()
even = 0
for (k, v) in cnt:
	if v % 2 == 0:
		even += 1
print(len(set(A)) - even % 2)


n = int(input())
A = tuple(map(int, input().split()))
from collections import Counter
CA = Counter(A)
cu2 = 0
for (k, v) in list(CA.items()):
	cu2 += v - 1
print(len(A) - cu2 - cu2 % 2)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A).items()
M = len(C)
print(M if (N - M) % 2 == 0 else M - 1)


def main():
	N = int(input())
	A = [int(a) for a in input().split(' ')]
	A.sort()
	cnt = []
	c = 0
	a = 0
	for i in range(len(A)):
		if i == 0:
			a = A[i]
			c += 1
		elif A[i] == a:
			c += 1
		elif A[i] != a:
			cnt.append(c)
			c = 1
			a = A[i]
	else:
		cnt.append(c)
	cnt = list(map(lambda ct: 2 - ct % 2, cnt))
	evens = cnt.count(2)
	if evens % 2 == 0:
		print(len(cnt))
	else:
		print(len(cnt) - 1)
main()


N = int(input())
A = list(map(int, input().split()))
kinds = set(A)
dif = N - len(kinds)
if dif % 2 == 0:
	print(len(kinds))
else:
	print(len(kinds) - 1)


N = int(input())
(*A,) = map(int, input().split())
a = set(A)
print(len(a) - (1 - len(a) % 2))


import sys
import math
N = int(input())
array = list(map(int, input().split()))
set_array = set(array)
if not (3 <= N <= 10 ** 5 and N % 2 == 1):
	return
print(len(list(set_array))) if len(list(set_array)) % 2 == 1 else print(len(list(set_array)) - 1)


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
b = Counter(a)
ans = 0
for i in b:
	if b[i] % 2 == 0:
		ans += 1
print(len(set(a)) - ans % 2)


N = int(input())
A = [int(a) for a in input().split()]
z = {}
for n in A:
	if n in z:
		z[n] += 1
	else:
		z[n] = 1
cnt_even = 0
for (key, val) in list(z.items()):
	if val % 2 == 0:
		cnt_even += 1
cnt_odd = len(z) - cnt_even
tot = cnt_odd + cnt_even - cnt_even % 2
print(tot)


N = int(input())
A = list(map(int, input().split()))
M = len(set(A))
from math import ceil
print(N - ceil((N - M) / 2) * 2)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
cnt = 0
for v in C.values():
	if v > 1:
		cnt += v - 1
if cnt % 2 == 0:
	print(N - cnt)
else:
	print(N - cnt - 1)


n = int(input())
a = list(map(int, input().split()))
t = set(a)
if len(t) % 2 == 0:
	print(len(t) - 1)
else:
	print(len(t))


N = int(input())
A = list(map(int, input().split()))
R = {}
for i in A:
	if i in R:
		R[i] += 1
	else:
		R[i] = 1
ans = len(R)
print(ans - (1 - ans % 2))


N = int(input())
L = list(map(int, input().split()))
s = len(set(L))
if s % 2 == 0:
	s -= 1
print(s)


n = int(input())
a = list(map(int, input().split()))
k = len(set(a))
if k % 2:
	ans = k
else:
	ans = k - 1
print(ans)


import sys
sys.setrecursionlimit(10 ** 8)

def ii():
	return int(sys.stdin.readline())

def mi():
	return map(int, sys.stdin.readline().split())

def li():
	return list(map(int, sys.stdin.readline().split()))

def li2(N):
	return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

def dp2(ini, i, j):
	return [[ini] * i for _ in range(j)]

def dp3(ini, i, j, k):
	return [[[ini] * i for _ in range(j)] for _ in range(k)]
from collections import defaultdict
N = ii()
A = li()
d = defaultdict(int)
for num in A:
	d[num] += 1
flag = 0
cnt = 0
for (key, value) in d.items():
	if value > 1:
		flag = (flag + value - 1) % 2
	cnt += 1
print(cnt - flag)


input()
a = len(set(input().split()))
print(a - 1 + a % 2)


N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = len(set(A))
if ans % 2 == 0:
	print(ans - 1)
else:
	print(ans)


input()
A = list(map(int, input().split()))
a = len(set(A))
res = len(A) - a
print(a - 1) if res % 2 else print(a)


from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
d = defaultdict(int)
for x in A:
	d[x] += 1
cnt = 0
for x in d:
	if d[x] >= 2 and d[x] % 2 == 0:
		cnt += 1
ans = len(d.keys())
if cnt % 2 == 1:
	ans -= 1
print(ans)


from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
d = defaultdict(int)
for i in range(N):
	if d[A[i]] == 0:
		d[A[i]] = 1
	else:
		d[A[i]] += 1
sorted_d = sorted(list(d.items()), key=lambda x: x[1], reverse=True)
fix_d = []
for i in range(len(sorted_d)):
	if sorted_d[i][1] >= 3:
		if sorted_d[i][1] % 2 == 0:
			fix_d.append([sorted_d[i][0], 2])
		else:
			fix_d.append([sorted_d[i][0], 1])
	else:
		fix_d.append([sorted_d[i][0], sorted_d[i][1]])
fix_d.sort(key=lambda x: x[1], reverse=True)
count = 0
for i in range(len(fix_d)):
	if fix_d[i][1] == 2:
		count += 1
if count % 2 == 0:
	print(len(fix_d))
else:
	print(len(fix_d) - 1)


N = int(input())
A = list(map(int, input().split()))
A.sort()
dp = [0] * (10 ** 5 + 1)
bp = []
for i in range(N):
	if dp[A[i]] != 0:
		bp.append(A[i])
	dp[A[i]] += 1
bp.sort()
p = len(bp)
q = p
o = 0
for i in range(10 ** 5):
	if p < 3:
		break
	p -= 2
if p == 0:
	N -= q
elif p == 1:
	N = N - q - 1
else:
	N = N - q
print(N)


N = int(input())
A = map(int, input().split())
d = [0 for i in range(10 ** 5 + 1)]
for a in A:
	d[a] = 1
l = [x for x in d if x]
print(len(l) - (0 if len(l) % 2 else 1))


import collections
n = int(input())
a = list(map(int, input().split()))
d = set(a)
c = collections.Counter(a)
b = 0
for i in c:
	if c[i] >= 2:
		b += c[i] - 1
if b % 2 == 1:
	ans = len(d) - 1
else:
	ans = len(d)
print(ans)


n = int(input())
a = set(map(int, input().split()))
kinds = len(a)
if kinds % 2 == 1:
	print(kinds)
else:
	print(kinds - 1)


from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
c_value = list(c.values())
overflow = sum(c_value) - len(c_value)
if overflow % 2 == 0:
	print(len(c_value))
else:
	print(len(c_value) - 1)


n = int(input())
a = list(map(int, input().split()))
from collections import Counter
c = Counter(a)
even_cnt = sum([cnt % 2 == 0 for (i, cnt) in c.items()])
if even_cnt % 2:
	print(len(c) - 1)
else:
	print(len(c))


N = int(input())
K = len(set(list(map(int, input().split()))))
if K % 2 == 0:
	print(K - 1)
else:
	print(K)


from collections import Counter
n = int(input())
A = sorted(list(map(int, input().split())))
C = Counter(A)
r = 0
for v in C.values():
	r += v - 1
print(len(C) - r % 2)


N = int(input())
A = list(map(int, input().split()))
s = set(A)
k = len(s)
if k % 2:
	ans = k
else:
	ans = k - 1
print(ans)


import collections
N = int(input())
AN = list(map(int, input().split()))
an = collections.Counter(AN)
a = sorted(list(an.values()), reverse=True)
al = len(a)
print(al if al % 2 == 1 else al - 1)


N = int(input())
A = [int(Ai) for Ai in input().split()]
cards = len(set(A))
print(cards if cards % 2 == 1 else cards - 1)


a = int(input())
x = list(map(int, input().split()))
y = set(x)
if len(y) % 2 == 0:
	print(len(y) - 1)
else:
	print(len(y))


def abc053_d():
	_ = int(input())
	A = list(map(int, input().split()))
	ans = 0
	from collections import Counter
	multi_even = 0
	for (_, v) in Counter(A).items():
		ans += 1
		if 2 <= v and v % 2 == 0:
			multi_even += 1
	if 0 < multi_even and multi_even % 2 == 1:
		ans -= 1
	print(ans)
abc053_d()


input()

def unique(seq):
	return {}.fromkeys(seq).keys()
cards = len(unique([Ai for Ai in input().split()]))
print(cards if cards % 2 == 1 else cards - 1)


from collections import defaultdict
n = int(input())
a_list = [int(x) for x in input().split()]
d = defaultdict(int)
for a in a_list:
	d[a] += 1
print(len(d.keys()) - sum([1 for v in d.values() if v % 2 == 0]) % 2)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
ans = len(C)
if (N - ans) % 2 == 1:
	ans -= 1
print(ans)


(_, a) = open(0)
k = len(set(a.split()))
print(k - 1 + k % 2)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
ct = 0
for i in C:
	ct += C[i] - 1
ct += ct % 2 == 1
print(N - ct)


n = int(input())
(*q,) = map(int, input().split())
s = len(set(q))
print(s if s % 2 != 0 else s - 1)


N = int(input())
arr = list(map(int, input().split()))
print(N - -(-(N - len(set(arr))) // 2) * 2)


from collections import Counter
N = int(input())
A = sorted(list(map(int, input().split())))
edible = sum((i - 1 for i in Counter(A).values()))
print(len(set(A)) - edible % 2)


n = int(input())
a = [int(x) for x in input().split()]
ac = list(set(a))
d = len(a) - len(ac)
ans = len(a) - d
if d % 2 == 1:
	ans -= 1
print(ans)


N = int(input())
A = map(int, input().split())
m = {}
eat = 1
for a in A:
	if a in m:
		eat += 1
	else:
		m[a] = 1
print(N - 2 * (eat // 2))


n = int(input())
a = list(map(int, input().split()))
from collections import Counter
ac = Counter(a)
count = 0
temp = 0
for i in ac:
	if ac[i] >= 3:
		if ac[i] % 2 == 0:
			count += ac[i] - 2
			ac[i] = 2
		else:
			count += ac[i] - 1
			ac[i] = 1
for j in ac:
	if ac[j] == 2:
		temp += 1
if temp % 2 == 0:
	count += temp
else:
	count += temp + 1
print(n - count)


from sys import stdin
from collections import Counter

def main():
	readline = stdin.readline
	n = int(readline())
	a = list(map(int, readline().split()))
	c = Counter(a)
	ans = n
	cnt_two = 0
	for key in c.keys():
		if c[key] >= 3:
			if c[key] % 2 == 1:
				ans -= c[key] - 1
				c[key] = 1
			else:
				ans -= c[key] - 2
				c[key] = 2
				cnt_two += 1
		elif c[key] == 2:
			cnt_two += 1
	if cnt_two % 2 == 0:
		ans -= cnt_two
	else:
		ans -= cnt_two - 1
		ans -= 2
	print(ans)

def __starting_point():
	main()
__starting_point()


n = int(input())
a = list(map(int, input().split()))
x = len(list(set(a)))
if x % 2 == 1:
	print(x)
else:
	print(x - 1)


import collections
N = int(input())
lsA = list(map(int, input().split()))
counterA = collections.Counter(lsA)
lsn = list(counterA.values())
rep = 0
even = 0
for i in lsn:
	if i % 2 == 1:
		rep += i // 2
	else:
		rep += (i - 1) // 2
		even += 1
rep += -(-even // 2)
ans = N - rep * 2
print(ans)


N = int(input())
A = list(map(int, input().split()))
S = set(A)
ans = len(S)
if (N - ans) % 2 == 1:
	ans -= 1
print(ans)


from collections import Counter
import sys
N = int(input())
cards = list(map(int, sys.stdin.readline().strip().split()))
c = Counter(cards)
even = len([x for x in iter(c) if c[x] % 2 == 0])
odd = len([x for x in iter(c) if c[x] % 2 == 1])
print(even - even % 2 + odd)


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


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
ans = len(cnt)
if ans % 2 == 0:
	print(ans - 1)
else:
	print(ans)


(n, *a) = map(int, open(0).read().split())
s = len(set(a))
print(s if (n - s) % 2 == 0 else s - 1)


n = int(input())
a = list(map(int, input().split()))
nums = [0] * 100005
for x in a:
	nums[x] += 1
(even, odd) = ([], [])
for p in nums:
	if p % 2 == 1 and p > 1:
		odd.append(p)
	elif p % 2 == 0 and p > 0:
		even.append(p)
ans = n
for x in odd:
	ans -= x - 1
if len(even) % 2 == 1:
	ans -= 1
for x in even:
	ans -= x - 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
A_set = set(A)
ans = len(A_set)
if ans % 2 == 0:
	ans -= 1
print(ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left, bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil, pi, factorial
from operator import itemgetter

def I():
	return int(input())

def MI():
	return list(map(int, input().split()))

def LI():
	return list(map(int, input().split()))

def LI2():
	return [int(input()) for i in range(n)]

def MXI():
	return [[LI()] for i in range(n)]

def SI():
	return input().rstrip()

def printns(x):
	print('\n'.join(x))

def printni(x):
	print('\n'.join(list(map(str, x))))
inf = 10 ** 17
mod = 10 ** 9 + 7
n = I()
lis = LI()
c = Counter(lis)
sm = 0
for i in list(c.keys()):
	sm += c[i] - 1
if sm % 2 == 0:
	print(len(list(c)))
else:
	print(len(list(c)) - 1)


input()
k = len(set(input().split()))
print(k - 1 + k % 2)


from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
cnt = Counter(a)
l = len(cnt)
even = 0
for v in cnt.values():
	if v % 2 == 0:
		even += 1
print(l if even % 2 == 0 else l - 1)


x = int(input())
a = list(map(int, input().split()))
b = list(set(a))
y = len(b)
print(x - (x - y) - (x - y) % 2)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
num = len(Counter(A))
print(num - (N - num) % 2)


import math
from math import gcd, pi, sqrt
INF = float('inf')
import sys
sys.setrecursionlimit(10 ** 6)
import itertools
from collections import Counter, deque

def i_input():
	return int(input())

def i_map():
	return list(map(int, input().split()))

def i_list():
	return list(i_map())

def i_row(N):
	return [i_input() for _ in range(N)]

def i_row_list(N):
	return [i_list() for _ in range(N)]

def s_input():
	return input()

def s_map():
	return input().split()

def s_list():
	return list(s_map())

def s_row(N):
	return [s_input for _ in range(N)]

def s_row_str(N):
	return [s_list() for _ in range(N)]

def s_row_list(N):
	return [list(s_input()) for _ in range(N)]

def main():
	n = i_input()
	l = i_list()
	dic = {}
	for i in l:
		dic[i] = dic.get(i, 0) + 1
	t = 0
	for (i, k) in list(dic.items()):
		t += k - 1
	if t % 2 == 0:
		print(len(dic))
	else:
		print(len(dic) - 1)

def __starting_point():
	main()
__starting_point()


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
len_set = len(list(set(A)))
CA = Counter(A)
count = 0
for (i, j) in CA.items():
	if j % 2 == 0:
		count += 1
if count % 2 == 0:
	ans = len_set
else:
	ans = len_set - 1
print(ans)


N = int(input())
A = [int(x) for x in input().split()]

def count(n, Set):
	if not n in Set:
		Set.add(n)
		return 0
	else:
		return 1
Sieve = set()
extra = 0
for a in A:
	extra += count(a, Sieve)
print(N - extra if not extra & 1 else N - extra - 1)


from collections import Counter
n = int(input())
c = Counter(input().split())
ans = 0
d = 0
for i in c.values():
	ans += i // 2
	d += int(i % 2 == 0)
print(n - 2 * (ans - d // 2))


(n, *l) = map(int, open(0).read().split())
from collections import *
c = Counter(l)
print(len(c) - sum((1 - v % 2 for v in c.values())) % 2)


N = int(input())
a = list(map(int, input().split()))
seta = set(a)
if len(seta) % 2 != 0:
	print(len(seta))
else:
	print(len(seta) - 1)


(n, *a) = map(int, open(0).read().split())
k = len(set(a))
print(k - (n - k) % 2)


n = int(input())
c = len(set([int(x) for x in input().split()]))
if (n - c) % 2 == 1:
	c -= 1
print(c)


print((lambda N, A: len(set(A)) - (N - len(set(A))) % 2)(int(input()), list(map(int, input().split()))))


(_, *l) = map(int, open(0).read().split())
c = len(set(l))
print(c - 1 + c % 2)


N = int(input())
cnt = [0] * (10 ** 5 + 1)
A = [int(_) for _ in input().split()]
for i in range(N):
	cnt[A[i]] += 1
m = 0
for i in range(10 ** 5 + 1):
	if cnt[i] > 0 and cnt[i] % 2 == 0:
		m += 1
print(len(set(A)) - int(m % 2 == 1))


N = int(input())
a = list(map(int, input().split()))
a.sort()
uni_a = set(a)
deleted = len(a) - len(uni_a)
print(len(a) - deleted - deleted % 2)


N = int(input())
A = list(map(int, input().split()))
A.sort()
d = []
for i in range(N - 1):
	if A[i] == A[i + 1]:
		d.append(A[i])
print(N - len(d) if len(d) % 2 == 0 else N - len(d) - 1)


n = input()
n = int(n)
a = input().split()
a = [int(x) for x in a]
b = set(a)
res = len(b)
if n % 2 != res % 2:
	res -= 1
print(res)


N = int(input())
A = list(map(int, input().split()))
As = set(A)
print(len(As) - (N - len(As)) % 2)


N = int(input())
As = list(map(int, input().split()))
ss = set(As)
r = len(ss) if len(ss) % 2 == 1 else len(ss) - 1
print(r)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
d = dict(Counter(A))
kaburi = 0
for key in d:
	kaburi += d[key] - 1
print(N - (kaburi % 2 + kaburi))


N = int(input())
List = list(map(int, input().split()))
sorts = len(set(List))
if (N - sorts) % 2 == 0:
	print(sorts)
else:
	print(sorts - 1)


n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
for i in range(1, len(a)):
	if a[i] == a[i - 1]:
		ans += 1
print(n - (ans + 1) // 2 * 2)


n = input()
A = list(map(int, input().split()))
l = len(set(A))
if l % 2 == 0:
	l -= 1
print(l)


n = int(input())
a = list(map(int, input().split()))
kind = set(a)
num = len(kind)
diff = n - num
div = (diff - 1) // 2
ans = n - 2 * (div + 1)
print(ans)


n = int(input())
card = list(map(int, input().split()))
c_set = set(card)
if len(c_set) % 2 != 0:
	print(len(c_set))
else:
	print(len(c_set) - 1)


n = int(input())
A = list(map(int, input().split()))
A.sort()
m = 0
cnt = 0
for i in A:
	if m != i:
		m = i
		cnt += 1
if cnt % 2 == 0:
	cnt -= 1
print(cnt)


from math import *
n = int(input())
a = list(map(int, input().split()))
b = set(a)
c = len(a) - len(b)
k = ceil(c / 2)
print(len(a) - 2 * k)


(N, *A) = map(int, open(0).read().split())
A = len(set(A))
print((A - 1, A)[A & 1])


n = int(input())
a = list(map(int, input().split()))
d = {}
for i in a:
	if i in d:
		d[i] += 1
	else:
		d[i] = 0
s = sum(d.values())
if s % 2 == 0:
	print(n - s)
else:
	print(n - s - 1)


N = int(input())
lst = list(map(int, input().split()))
s = len(set(lst))
print((s - 1) // 2 * 2 + 1)


n = int(input())
a = list(map(int, input().split()))
a_unique = list(set(a))
x = len(a) - len(a_unique)
print(len(a_unique) - x % 2)


from collections import defaultdict
import heapq
N = int(input())
alist = list(map(int, input().split()))
adic = defaultdict(int)
for a in alist:
	adic[a] += 1
hq = []
for (k, b) in adic.items():
	heapq.heappush(hq, (-b, k))
cnt = 0
while True:
	(mf, n) = heapq.heappop(hq)
	if mf == -1:
		break
	elif mf <= -3:
		heapq.heappush(hq, (mf + 2, n))
		cnt += 1
	else:
		(mf2, n2) = heapq.heappop(hq)
		if mf2 == -1:
			cnt += 1
			break
		else:
			heapq.heappush(hq, (mf + 1, n))
			cnt += 1
print(N - 2 * cnt)


n = int(input())
import collections
co = collections.Counter(map(int, input().split()))
r = 0
for cnt in co.values():
	r += cnt - 1
if r % 2 == 0:
	print(n - r)
else:
	print(n - r - 1)


N = int(input())
A = list(map(int, input().split()))
A.sort()
cnt = 0
buf = 0
for a in A:
	if buf != a:
		cnt += 1
	buf = a
print((cnt - 1) // 2 * 2 + 1)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
C = sorted(C.items())
cc = []
for (a, b) in C:
	cc.append([a, b])
C = cc
M = len(C)
left = 0
right = M - 1
while True:
	if C[left][1] < 2:
		p_left = left
		for left in range(p_left, M):
			if C[left][1] > 1:
				break
	if C[right][1] < 2:
		p_right = M - right - 1
		for right in range(M):
			if C[M - right - 1][1] > 1:
				break
		right = M - right - 1
	if C[left][1] <= 1 and C[right][1] <= 1:
		break
	if left == right:
		if C[left][1] >= 3:
			C[left][1] -= 2
		else:
			f = 0
			C[left][1] -= 1
			for i in range(left + 1, M):
				if C[i][1] > 0:
					C[i][1] -= 1
					f = 1
					break
			if f == 0:
				for i in range(0, left):
					if C[i][1] > 0:
						C[i][1] -= 1
	else:
		C[left][1] -= 1
		C[right][1] -= 1
ans = 0
for (a, b) in C:
	ans += b
print(ans)


N = int(input())
A = list(sorted(map(int, input().split()), reverse=True))
from collections import Counter
cnt_a = Counter(A)
X = [0] * 3
for (k, v) in list(cnt_a.items()):
	while v >= 3:
		v = v // 3 + v % 3
	X[v] += 1
if X[2] % 2 == 0:
	print(X[1] + X[2])
else:
	print(X[1] - 1 + X[2])


n = int(input())
L = list(map(int, input().split()))
L.sort()
from collections import Counter
L = Counter(L)
cnt = 0
one = 0
for v in L.values():
	if v % 2 == 0:
		cnt += 1
	else:
		one += 1
if cnt % 2 == 0:
	one += cnt
else:
	one += cnt - 1
print(one)


from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
s = len(set(A))
if s % 2 != 0:
	print(s)
else:
	print(s - 1)


n = int(input())
l = len(set(map(int, input().split())))
print(l - (n - l) % 2)


input()
c = len(set(input().split()))
print(c - 1 + c % 2)


n = int(input())
A = list(map(int, input().split()))
B = set(A)
s = len(B)
if s % 2 == 0:
	print(s - 1)
else:
	print(s)


N = int(input())
A = list(map(int, input().split()))
if len(A) == 3:
	print(1)
elif (len(A) - len(set(A))) % 2 == 1:
	print(len(set(A)) - 1)
else:
	print(len(set(A)))


n = int(input())
a = [int(j) for j in input().split()]
tmp = len(set(a))
while n > tmp:
	n -= 2
print(n)


n = int(input())
t = list(map(int, input().split()))
memo = [0] * 100000
for i in t:
	memo[i - 1] += 1
sa = 0
for j in memo:
	if 1 < j:
		sa += j - 1
print(n - sa - sa % 2)


n = int(input())
a = list(map(int, input().split()))
adict = {}
for c in a:
	adict[c] = adict.get(c, 0) + 1
twos = 0
moreodd = 0
moreeven = 0
for num in adict.keys():
	if adict[num] == 2:
		twos += 1
	elif adict[num] > 2:
		if adict[num] % 2 == 0:
			moreeven += 1
		else:
			moreodd += 1
if moreeven % 2 == 1:
	twos += 1
if twos % 2 == 0:
	print(len(adict))
else:
	print(len(adict) - 1)


from collections import Counter
N = int(input())
A = [int(s) for s in input().split()]
c = Counter(A)
b = [n - 1 for (v, n) in c.items() if n > 1]
ans = len(c) - sum(b) % 2
print(ans)


from collections import Counter
n = int(input())
A = map(int, input().split())
k = len(Counter(A))
print(k if k % 2 != 0 else k - 1)


from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
v = sum(map(lambda x: x - 1, c.values()))
if v % 2 == 0:
	print(len(c))
else:
	print(len(c) - 1)


N = int(input())
A = list(map(int, input().split()))
S = {}
for i in range(N):
	if A[i] in S:
		S[A[i]] += 1
	else:
		S[A[i]] = 1
d = 0
for i in S.values():
	d += i - 1
print(len(set(A)) - d % 2)


from collections import Counter
N = int(input())
eaten = N - len(Counter(map(int, input().split())))
eaten += eaten & 1
print(N - eaten)


N = int(input())
A = [int(i) for i in input().split()]
if len(set(A)) % 2 == 0:
	print(len(set(A)) - 1)
else:
	print(len(set(A)))


from collections import Counter
(N, *A) = map(int, open(0).read().split())
ac = Counter(A)
e = [x[0] for x in ac.items() if x[1] % 2 == 0]
if len(e) % 2 == 0:
	print(len(ac))
else:
	print(len(ac) - 1)


input()
cards = len(set([Ai for Ai in input().split()]))
print(cards if cards % 2 == 1 else cards - 1)


import sys
input = lambda : sys.stdin.readline()
import collections
n = int(input())
a = sorted(list(map(int, input().split())))
d = collections.Counter(a)
need = {}
for (k, v) in list(d.items()):
	if v > 1:
		need[k] = v
if (sum(list(need.values())) - len(need)) % 2 == 0:
	print(len(set(a)))
else:
	print(len(set(a)) - 1)


from collections import Counter
input()
A = list(map(int, input().split()))
c = Counter(A)
lenc = len(c)
print(lenc - 1 if lenc & 1 == 0 else lenc)


N = int(input())
A = list(map(int, input().split()))
from collections import Counter

def check(counter, A):
	return len(counter) != len(A)

def Main(N, A):
	counter = Counter(A)
	lenC = len(counter)
	remains = N - lenC
	if remains % 2 == 0:
		return lenC
	else:
		return lenC - 1
print(Main(N, A))


n = int(input())
a = list(map(int, input().split()))
num = [0] * 100001
for i in a:
	num[i] += 1
x = 0
for i in num:
	if i <= 0:
		continue
	elif i % 2 == 0:
		n -= i
		x += 1
	else:
		n -= i - 1
if x % 2:
	x -= 1
print(n + x)


import sys
from collections import Counter
input = sys.stdin.readline

def main():
	n = int(input())
	a = list(map(int, input().split()))
	a = Counter(a)
	other = 0
	ans = n
	for (k, v) in list(a.items()):
		ans -= v - 1
		if not v % 2:
			other += 1
	ans -= other % 2
	print(ans)

def __starting_point():
	main()
__starting_point()


n = int(input())
A = list(map(int, input().split()))
m = n - len(set(A))
print(n - m - (m % 2 == 1))


i = int(input())
s = list(input().split())
a = len(set(s))
if a % 2 == 0:
	a -= 1
print(a)


import io
data = int(input())
array = list(map(int, input().split()))
strings = len(set(array))
if data % 2 == strings % 2:
	print(strings)
else:
	print(strings - 1)


import collections
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
most = c.most_common()
ans = len(most)
eaten = 0
for t in most:
	if t[1] != 1:
		eaten += t[1] - 1
if eaten % 2 == 1:
	print(ans - 1)
else:
	print(ans)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
eat = 0
for v in c.most_common():
	if v[1] >= 2:
		eat += v[1] - 1
if eat % 2 != 0:
	eat += 1
print(N - eat)


n = int(input())
a = list(map(int, input().split()))
aset = set(a)
la = len(aset)
if la % 2 == 0:
	print(la - 1)
else:
	print(la)


N = int(input())
card = set([int(i) for i in input().split()])
if len(card) % 2 == 1:
	print(len(card))
else:
	print(len(card) - 1)


n = int(input())
a = list(map(lambda x: int(x), input().split()))
dic = {}
for i in a:
	dic.setdefault(i, True)
tmp = len(dic)
ans = tmp if tmp % 2 == 1 else tmp - 1
print(ans)


n = int(input())
card_ls = list(map(int, input().split()))
card_ls.sort()
have_to_eat = 0
for i in range(1, n):
	if card_ls[i - 1] == card_ls[i]:
		have_to_eat += 1
if have_to_eat % 2 == 1:
	have_to_eat += 1
ans = n - have_to_eat
print(ans)


N = int(input())
A = [int(x) for x in input().split()]
from collections import defaultdict as dd
Sieve = dd(lambda : 0)
for a in A:
	Sieve[a] += 1
(ans, extra) = (0, 0)
for v in list(Sieve.values()):
	ans += 1
	if v > 1 and v - 1 & 1:
		extra += 1
print(ans if not extra & 1 else ans - 1)


from collections import Counter
N = int(input())
a = list(map(int, input().split()))
na = len(set(a))
cnt = Counter(a)
ls = cnt.most_common()
lst = [2 for i in ls if i[1] % 2 == 0]
if len(lst) % 2 == 1:
	print(na - 1)
else:
	print(na)


input()
a = list(map(int, input().split()))
c = {}
lb = lc = 0
for i in a:
	try:
		c[i] += 1
		lb += 1
	except:
		c[i] = 1
		lc += 1
print(lc if lb % 2 == 0 else lc - 1)


N = int(input())
A = [int(x) for x in input().split()]
x = len(set(A))
answer = x
if x % 2 == 0:
	answer -= 1
print(answer)


N = int(input())
A = list(map(int, input().split()))
uniq = set(A)
l = len(uniq)
if l % 2 == 0:
	print(str(l - 1))
else:
	print(str(l))


from collections import Counter
N = int(input())
cards = list(map(int, input().split()))
counter = Counter(cards)
ans = len(counter)
rest = 0
for (num, cnt) in counter.items():
	rest += cnt - 1
if rest % 2 == 1:
	ans -= 1
print(ans)


n = int(input())
ai = [int(i) for i in input().split()]
ans = len(set(ai))
if ans % 2 == 1:
	print(ans)
else:
	print(ans - 1)


N = int(input())
A = map(int, input().split())
d = N - len(set(A))
print(N - (d + 1) // 2 * 2)


n = int(input())
a = list(input().split())
b = len(set(a))
print(b - 1 + b % 2)


n = int(input())
a = list(input().split())
ans = len(set(a))
if ans % 2 == 0:
	ans -= 1
print(ans)


N = int(input())
A = set(map(int, input().split()))
r = N - len(A)
print(N - int(r / 2 + 1 / 2) * 2)


n = int(input())
a = [int(x) for x in input().split()]
s = set(a)
l = len(s)
l2 = 0 if l % 2 else 1
print(l - l2)


N = int(input())
A = list(map(int, input().split()))
A_set = set(A)
eat = len(A) - len(A_set)
if eat % 2 == 0:
	print(len(A_set))
else:
	print(len(A_set) - 1)


import collections
n = int(input())
s = list(map(int, input().split()))
k = len(collections.Counter(s))
if (n - k) % 2 == 0:
	print(k)
else:
	print(k - 1)


n = int(input())
A = list(map(int, input().split()))
A_set = set(A)
if (len(A) - len(A_set)) % 2 == 0:
	ans = len(A_set)
else:
	ans = len(A_set) - 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
ans = len(set(A)) - (len(A) - len(set(A))) % 2
print(ans)


n = int(input())
a = list(map(int, input().split()))
i = len(a)
s = set(a)
j = len(s)
if (i - j) % 2 == 0:
	print(n - (i - j))
else:
	print(n - (i - j + 1))


import collections
_ = input()
an = sorted([int(i) for i in input().split(' ')])
c = collections.Counter(an)
print(len(c) - (len(c) + 1) % 2)


from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
dict = defaultdict(int)
for a in A:
	dict[a] += 1
num = [0] * 2
for v in dict.values():
	num[v % 2] += 1
if num[0] % 2 == 0:
	print(sum(num))
else:
	print(sum(num) - 1)


def resolve():
	N = int(input())
	A = list(map(int, input().split(' ')))
	import collections
	cnter = collections.Counter(A)
	evens = 0
	for i in list(cnter.values()):
		if i % 2 == 0:
			evens += 1
	print(len(cnter) - 1 if evens % 2 == 1 else len(cnter))

def __starting_point():
	resolve()
__starting_point()


n = int(input())
a = list(map(int, input().split()))
a.sort()
from collections import Counter
a = Counter(a)
csum = 0
for (i, icnt) in a.most_common():
	csum += icnt - 1
if csum % 2 == 1:
	csum += 1
print(n - csum)


import sys
read = sys.stdin.read
readlines = sys.stdin.readlines

def main():
	(n, *a) = map(int, read().split())
	r = len(set(a))
	r -= n - r & 1
	print(r)

def __starting_point():
	main()
__starting_point()


from collections import Counter
n = int(input())
a = Counter(list(map(int, input().split()))).values()
s = sum([b - 1 for b in a if b > 1])
print(n - s - s % 2)


import collections
n = int(input())
A = list(map(int, input().split()))
print(len(collections.Counter(A)) - (n - len(collections.Counter(A))) % 2)


N = int(input())
K = len(set(input().split()))
print(K + K % 2 - 1)


N = int(input())
nums = list(map(int, input().split()))
unit = set(nums)
if len(unit) % 2 == 0:
	print(len(unit) - 1)
else:
	print(len(unit))


from collections import Counter
n = int(input())
m = sum((v - 1 for v in Counter([int(i) for i in input().split()]).values()))
print(n - round(m + 0.5))


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
c = 0
for (k, v) in C.items():
	c += v - 1
if c % 2 == 1:
	c += 1
print(N - c)