Paint and Conquer

Limits: 4 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk has an array \(a\) of \(n\) elements, where \(n\) is divisible by 4. But he also wants to form a graph with \(n\) vertices. He adds an edge between vertices \(v\) and \(u\) (\(v \ne u\)) if \(a_v\) \(\&\) \(a_u \ne 0\), where \(\&\) is the bitwise AND operation.

Marichka wants to remove all edges in Zenyk’s graph. To do this, in one minute she can paint exactly \(\frac{n}{2}\) vertices blue, the remaining vertices yellow, and remove all edges that run between vertices of the same color.

Help Marichka determine the minimum number of minutes she needs to remove all edges.

Input

The first line contains a single integer \(n\). The second line contains \(n\) integers \(a_i\).

Output

Print a single number — the minimum number of minutes required to remove all edges.

Constraints

\(4 \le n \le 2 \cdot 10^5\), \(n\) is divisible by 4,

\(0 \le a_i < 2^{18}\).

Samples