Double Up

Interview

Time limit2sMemory limit1024 MB

Summary

Each number can only be doubled into values that share its odd part, so the task is to find the largest group of numbers with the same odd part.

Level: Easy3 of 10
Topics: Math, Hash map
Solved: No attempts yet

Problem

You are given a sequence $A$ of $N$ positive integers. Dal-gu can pick one number from this sequence and multiply it by $2$ . He can repeat this operation as many times as he wants.

After Dal-gu finishes all operations, let $k$ be the number that appears most often in the array. If several numbers tie for the most appearances, $k$ is the largest of them. Find the maximum possible number of appearances of $k$ .

Input

The first line contains the length of the sequence $N$ . $(1 \le N \le 200\ 000)$

The second line contains $N$ positive integers $A_1, A_2, \cdots, A_N$ separated by spaces. $(1 \le A_i \le 10^9)$

Output

After performing any number of operations, print the maximum possible number of appearances of the most frequent number in the array.

Examples2

Example 1
Input
```
4
5 10 15 20
```
Expected output
```
3
```
Example 2
Input
```
9
3 1 4 1 5 9 2 6 3
```
Expected output
```
4
```