C. Count Pairs
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a sequence of positive integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$.

A pair of integers $$$x, y$$$ is good if $$$\max(x, y) \lt x \oplus y$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

A set $$$S$$$ of integers counts if all its elements are unique, and all pairs of distinct integers in $$$S$$$ are good.

What is the largest subset of $$$a_1, a_2, \ldots, a_n$$$ that counts?

Input

The first line contains $$$n$$$ ($$$1 \leq n \leq 3\cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 4\cdot 10^6$$$).

Output

Print the size of the largest subset of $$$a_1, a_2, \ldots, a_n$$$ that counts.

Examples
Input
3
1 2 3
Output
2
Input
3
4000000 4000000 4000000
Output
1
Note

In the first test, the set $$$\{1,2\}$$$ counts, since $$$1 \oplus 2 = 3$$$, while $$$\max(1, 2) = 2$$$, and $$$3 \gt 2$$$. However, $$$\{1,2,3\}$$$ does not count, since, for example, $$$1 \oplus 3 = 2 \leq \max(1,3) = 3$$$. So the answer is $$$2$$$.

In the second test, the optimal solution is to just take the set $$$\{4\,000\,000\}$$$.