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
from collections import Counter
import sys

def solve_example(c: Counter, n_ints: int) -> int:
    num_used = 0
    partitions = 0
    for _, cnt in c.most_common():
        partitions += 1
        num_used += 2*cnt - 1
        if num_used >= n_ints:
            break
    return partitions


if __name__ == "__main__":

    input_lines = [line for line in sys.stdin]
    n_examples = len(input_lines) // 2
    for i in range(n_examples):
        n_ints = int(input_lines[2*i])
        counts = Counter([int(x) for x in input_lines[2*i + 1].rstrip().split(" ")])

        n_needed = solve_example(counts, n_ints)
        print(n_needed)