Items

Time limit3sMemory limit1024 MB

Summary

Given item positions on a number line, find the most items Juwon can pick up when each pickup doubles the length of his moves.

Level: Medium6 of 10
Topics: Bit manipulation, Trie, Greedy
Solved: No attempts yet

Problem

An infinitely long number line has $N$ items lying on it. The position of the $i$ -th item is $X\_i$ , and several items may be at the same position. Juwon is at position $0$ and wants to pick up as many items as possible.

At first, each move takes Juwon 1 unit to the left or to the right. However, every time he picks up an item, the length of each move doubles. In other words, if he has picked up $k$ items so far, each move takes him $2^k$ units to the left or to the right. A move cannot be stopped partway.

An item can be picked up only when Juwon stops exactly at its position. Even when he stops at a position with an item, he may choose not to pick it up. When an item is picked up, it disappears from that position.

Find the maximum number of items Juwon can pick up.

Input

The first line contains the number of items $N$ .

The second line contains the positions of the items $X\_1, X\_2, \cdots, X\_N$ , separated by spaces.

Output

Print the maximum number of items that can be picked up.

Constraints

$1\leq N\leq 2\times 10^5$
$0\leq X\_i\leq 10^{18}$ $(1\le i\le N)$
All input numbers are integers.

Hint

The input is large, so it is recommended to use the fast I/O described in the language guide on pages 2 to 4 of the problem set.

Examples3

Example 1
Input
```
5
0 1 3 8 9
```
Expected output
```
3
```
Example 2
Input
```
5
5 39 19 27 11
```
Expected output
```
5
```
Example 3
Input
```
3
0 0 1000000000000000000
```
Expected output
```
3
```