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
import sys

def moore(seq_length, seq):
    counter = 0
    element = -1

    for x in range(0, seq_length):
        count_array[seq[x]] += 1
        if counter == 0:
            element = seq[x]
            counter = 1
        elif element == seq[x]:
            counter += 1
        else:
            counter -=1
    
    occurence = seq.count(element)

    if occurence > seq_length / 2:
        return True
    else:
        return False
        

n = int(input())
sequence = [int(i) for i in input().split(" ")]
count_array = [0] * 500000

if moore(n,sequence):
    print(0)
    sys.exit(0)

count_array.sort(reverse=True) 

finished = False
number_of_split = 0
suffiecent_for = 0

while number_of_split<500000:
    suffiecent_for += count_array[number_of_split] * 2 - 1
    
    if suffiecent_for >= n:
         print(number_of_split + 1)
         sys.exit(0)
    else:
        number_of_split += 1
    
print(number_of_split)