Big Buckets

Problem Statement

You have a list of ~n~ numbers, labelled ~i_1~ to ~i_n~, that you're trying to put inside different buckets.

Each bucket can hold any amounts of numbers in it. However, for each bucket, strictly more than half of its content must be identical.

What is the minimum number of buckets needed to pack all ~n~ numbers?

Input

Your first line will contain the integer ~n~.

Your next ~n~ lines will contain one integer each, which are the numbers waiting to be put inside buckets.

Output

One line, containing the minimum number of buckets needed to pack all ~n~ numbers.

Constraints

For all test cases:

• ~1 \le n \le 10^{6}~
• ~1 \le i_1 ... i_n \le 10^{6}~

Sample Test Cases

Example 1

Input

5
4
7
4
3
2

Output

3

Explanation

In this scenario, the ~n = 5~ numbers can be put inside ~3~ buckets. One possible combination would be [2], [3], [4, 4, 7]. Each bucket has strictly more than half of the elements identical to each other.

Example 2

Input

8
3
5
12
3
3
5
3
4

Output

2

Explanation

In this scenario, the ~n = 8~ numbers can be put inside ~2~ buckets. One possible combination would be [3, 3, 3, 4, 12], [3, 5, 5].

Example 3

Input

9
6
23
6 
6
6
6
6
6
6

Output

1

Explanation

In this scenario, all ~n = 9~ numbers can be put inside the same bucket.

Python Template

n = map(int, input.split())
numbers = [int(input()) for _ in range(n)]