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
import numpy as np

n = input()
a = np.array(input().split(), int)
# a = np.random.randint(500000, size=500000)
unique, counts = np.unique(a, return_counts=True)

counts[::-1].sort()

iStart = 0
iEnd = counts.size - 1
result = 0
tmpSum = 0
countsIStart = counts[iStart]

while True:
    if iEnd <= iStart:
        result += 1
        break

    if countsIStart > tmpSum + counts[iEnd]:
        tmpSum += counts[iEnd]
        iEnd -= 1
    else:
        counts[iEnd] -= countsIStart - tmpSum - 1
        iStart += 1
        countsIStart = counts[iStart]
        tmpSum = 0
        result += 1

print(result)