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
n = int(input())

ciag = list(map(int, input().split(' ')))

occ = [0] * (n+1)

for i in range(n):
    occ[ciag[i]] += 1

cuts = 0

# i-ty element occ wystapil occ[i] razy

def doesOccArrHaveLeader(arr):
    ar = [e for e in arr if e != 0]
    return max(ar) > sum(ar) - max(ar)


while(True):
    if(doesOccArrHaveLeader(occ)): break

    m = occ.index(max(occ)) # liczba m wystapila najwiecej razy, occ[m] razy

    currentLen = occ[m]

    while(True):
        mi = occ.index(min(occ))
        if(currentLen + occ[mi] > occ[m] or mi == 0):
            break
        currentLen += occ[mi]
        occ[mi] = 0

    cuts += 1
    occ[m] = 0

print(cuts+1)