1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import sys

DEBUG = False

n = int(input())
aa = [0 for _ in range(n + 1)]

a = [int(i) for i in input().split(' ') if i != '']

for b in a:
    aa[b] += 1

if max(aa) > n // 2:
    print(1)
    sys.exit()
elif max(aa) == 1:
    print(n)
    sys.exit()

aa = [x for x in aa if x != 0]

aa.sort(reverse=True)
cc = list(aa)

k = 0
aalen = len(aa)
while k < aalen - 1:
    DEBUG and print("k: ", k)
    DEBUG and print("  ost: ", cc[aalen - 1])
    isDel = False
    for z in range(cc[aalen - 1], 0, -1):
        DEBUG and print("  z: ", z)
        if aa[k] > (cc[k] + z) // 2:
            cc[k] += z
            if z == cc[aalen - 1]:
                DEBUG and print('  del')
                del cc[aalen - 1]
                del aa[aalen - 1]
                aalen -= 1
                isDel = True
                break
            else:
                cc[aalen - 1] -= z
                aa[aalen - 1] -= z
            DEBUG and print("  done z :", z)
            break
    if not isDel:
        k += 1

print(len(aa))